BiruLyu
7/8/2017 - 5:22 AM

## 321. Create Maximum Number(1st).java

``````/**
* Created by hrwhisper on 2015/11/23.
* https://www.hrwhisper.me/leetcode-create-maximum-number/
*/

public class Solution {

private int[] get_candidates(int[] nums, int k) {
int n = nums.length;
if (n <= k) return nums;
int[] res = new int[k];
int len = 0;
for (int i = 0; i < nums.length; i++) {
while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
len--;
}
if (len < k)
res[len++] = nums[i];
}
return res;
}
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] ans = new int[k];
nums1 = get_candidates(nums1, k);
nums2 = get_candidates(nums2, k);
for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); i++) {
int[] res1 = get_max_sub_array(nums1, i);
int[] res2 = get_max_sub_array(nums2, k - i);
int[] res = new int[k];
int pos1 = 0, pos2 = 0, tpos = 0;

while (pos1 < res1.length || pos2 < res2.length) {
res[tpos++] = greater(res1, pos1, res2, pos2) ? res1[pos1++] : res2[pos2++];
}

if (!greater(ans, 0, res, 0))
ans = res;
}

return ans;
}

public boolean greater(int[] nums1, int start1, int[] nums2, int start2) {
for (; start1 < nums1.length && start2 < nums2.length; start1++, start2++) {
if (nums1[start1] > nums2[start2]) return true;
if (nums1[start1] < nums2[start2]) return false;
}
return start1 != nums1.length;
}

public int[] get_max_sub_array(int[] nums, int k) {
int[] res = new int[k];
int len = 0;
for (int i = 0; i < nums.length; i++) {
while (len > 0 && len + nums.length - i > k && res[len - 1] < nums[i]) {
len--;
}
if (len < k)
res[len++] = nums[i];
}
return res;
}
}``````
``````public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[][] dp1 = maxNumberForSingle(nums1, k);
int[][] dp2 = maxNumberForSingle(nums2, k);
int[] max = null;
for (int x = 0; x <= k; x++) {
if (x <= nums1.length && k-x <= nums2.length) {
max = max(max, merge(dp1[x], dp2[k-x]));
}
}
return max;
}

private int[] merge(int[] a1, int[] a2) {
int[] a = new int[a1.length + a2.length];
int i1 = 0, i2 = 0, i = 0;
while (i1 < a1.length || i2 < a2.length) {
if (i1 == a1.length) {
a[i++] = a2[i2++];
} else if (i2 == a2.length) {
a[i++] = a1[i1++];
} else if (greater(a1, a2, i1, i2)) {
a[i++] = a1[i1++];
} else {
a[i++] = a2[i2++];
}
}
return a;
}

private boolean greater(int[] a1, int[] a2, int i1, int i2) {
while (i1 < a1.length && i2 < a2.length) {
if (a1[i1] > a2[i2]) return true;
else if (a1[i1] < a2[i2]) return false;
else {
i1++;
i2++;
}
}
if (i1 < a1.length) return true;
else return false;
}

private int[][] maxNumberForSingle(int[] nums, int k) {
int [][][] dp = new int[2][k+1][];
for (int i = nums.length; i >= 0; i--) {
for (int x = 0; x <= k && x <= nums.length - i; x++) {
if (x == 0) {
dp[i%2][x] = new int[x];
} else {
if (x == nums.length - i) {
dp[i%2][x] = new int[x];
copy(dp[i%2][x], 1, dp[(i+1)%2][x-1]);
dp[i%2][x][0] = nums[i];
} else {
int[] opt1 = dp[(i+1)%2][x];
int[] opt2 = new int[x];
copy(opt2, 1, dp[(i+1)%2][x-1]);
opt2[0] = nums[i];
dp[i%2][x] = max(opt1, opt2);
}
}
}
}
return dp[0];
}

private void copy(int[] dest, int offset, int[] origin) {
for (int i = 0;i < origin.length; i++) {
dest[i + offset] = origin[i];
}
}

private int[] max(int[] a1, int[] a2) {
if (a1 == null) return a2;
if (a2 == null) return a1;
if (a1.length != a2.length) {
throw new IllegalArgumentException();
}
int i1 = 0;
int i2 = 0;
while (i1 < a1.length) {
if (a1[i1] > a2[i2]) return a1;
else if (a1[i1] < a2[i2]) return a2;
else {
i1++;
i2++;
}
}
return a1;
}``````
``````public class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length;
int n = nums2.length;
int[] ans = new int[k];
for (int i = 0; i <= k; i++) {
if (i <= m && k - i <= n) {
int[] array1 = maxNumberFromArray(nums1, i);
int[] array2 = maxNumberFromArray(nums2, k - i);
int[] merged = merge(array1, array2);
if (compareArray(merged, 0, ans, 0)) ans = merged;
}
}

return ans;
}

// compare int[] nums1 with int[] nums2
private boolean compareArray(int[] nums1, int s1, int[] nums2, int s2) {
int i = s1, j = s2;
int m = nums1.length, n = nums2.length;
while (i < m && j < n && nums1[i] == nums2[j]) {
i++;
j++;
}

// verbose
if ((i < m && j < n && nums1[i] > nums2[j]) || (i < m && j == n && nums1[i] >= nums1[s1])
|| (i == m && j < n && nums2[j] < nums2[s2])) return true;

return false;
}

// merge two num array
private int[] merge(int[] nums1, int[] nums2) {
int i = 0, j = 0, k = 0;
int m = nums1.length, n = nums2.length;
int[] ans = new int[m + n];
while (i < m && j < n) {
if (nums1[i] > nums2[j]) {
ans[k++] = nums1[i++];
}
else if (nums1[i] < nums2[j]) {
ans[k++] = nums2[j++];
}
else { // equal
if (compareArray(nums1, i, nums2, j)) ans[k++] = nums1[i++];
else ans[k++] = nums2[j++];
}
}

while (i < m) {
ans[k++] = nums1[i++];
}
while (j < n) {
ans[k++] = nums2[j++];
}

return ans;
}

// generate max k-digit number from one array
private int[] maxNumberFromArray(int[] nums, int k) {
int[] ans = new int[k];
int top = 0;
for (int i = 0; i < nums.length; i++) {
while (nums.length - i + top > k && top > 0 && nums[i] > ans[top - 1]) {
top--;
}
if (top < k) ans[top++] = nums[i];
}

return ans;
}
}``````