In this Leetcode Create Maximum Number problem solution You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k. Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved. Return an array of the k digits representing the answer.
Problem solution in Python.
class Solution(object): def maxNumber(self, nums1, nums2, k): l1,l2 = len(nums1),len(nums2) rs = [] def helper(nums,c_len): ans = [] ln = len(nums) for idx,val in enumerate(nums): while ans and ans[-1]<val and ln-idx> c_len-len(ans): ans.pop(-1) if len(ans)<c_len: ans.append(val) return ans for s1 in range(max(0,k-l2),min(k,l1)+1): p1,p2 = helper(nums1,s1),helper(nums2,k-s1) rs = max(rs,[max(p1,p2).pop(0) for _ in range(k)]) return rs
Problem solution in Java.
public class Solution { public int[] maxNumber(int[] nums1, int[] nums2, int k) { if (k==0) return new int[k]; if (nums1.length==0){ return getMaxNumberFromNums(nums2,k); } if (nums2.length==0){ return getMaxNumberFromNums(nums1,k); } int[] maxNum2 = getMaxNumberFromNums(nums2,Math.min(nums2.length,k)); Deque<int[]> maxNums2 = getMaxNumsForAllLenth(maxNum2,Math.max(k-nums1.length, 0)); int[] maxNum1 = getMaxNumberFromNums(nums1,Math.min(nums1.length,k)); int[] res = new int[k]; for (int len1 = Math.min(nums1.length,k);len1>=Math.max(k-nums2.length,0);len1--){ if (len1 < Math.min(nums1.length,k)){ maxNum1 = getMaxNumWithOneLessLen(maxNum1); } maxNum2 = maxNums2.pollFirst(); res = getNewMaxNumber(res,maxNum1,maxNum2); } return res; } public int[] getMaxNumberFromNums(int[] nums, int maxNumLen){ int[] maxNum = new int[maxNumLen]; int len = nums.length; int end = 0; for (int i=0;i<len;i++){ while (end >= 1 && maxNum[end-1] < nums[i] && len - i > maxNumLen - end){ end--; } if (end < maxNumLen) maxNum[end++] = nums[i]; } return maxNum; } public Deque<int[]> getMaxNumsForAllLenth(int[] maxNum, int minLen){ Deque<int[]> maxNums = new LinkedList<int[]>(); maxNums.add(maxNum); while (maxNum.length>minLen){ int[] nextNum = getMaxNumWithOneLessLen(maxNum); maxNums.addFirst(nextNum); maxNum = nextNum; } return maxNums; } public int[] getMaxNumWithOneLessLen(int[] maxNum){ int len = maxNum.length, end = 0; int[] nextNum = new int[len-1]; boolean deleted = false; for (int i=0;i<len;i++){ if (end >= len-1) break; if ((i==len-1 || maxNum[i] >= maxNum[i+1]) || deleted){ nextNum[end++] = maxNum[i]; } else { deleted = true; } } return nextNum; } public int[] getNewMaxNumber(int[] maxNum, int[] part1, int[] part2){ int[] newNum = new int[maxNum.length]; int p1 = 0, p2 = 0, index = 0; boolean newNumLarger = false; while (p1 < part1.length || p2 < part2.length){ newNum[index] = (greater(part1,p1,part2,p2)) ? part1[p1++] : part2[p2++]; if (maxNum[index] > newNum[index] && !newNumLarger){ return maxNum; } else if (maxNum[index] < newNum[index]){ newNumLarger = true; } index++; } return newNum; } public boolean greater(int[] part1, int p1, int[] part2, int p2){ while (p1<part1.length && p2<part2.length && part1[p1]==part2[p2]){ p1++; p2++; } return p2==part2.length || (p1 < part1.length && part1[p1] > part2[p2]); } }
Problem solution in C++.
class Solution { public: vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { vector<int> result (k, 0); vector<vector<int>> maxNumbers1=maxNumbers(nums1, min(k,(int)nums1.size())); vector<vector<int>> maxNumbers2=maxNumbers(nums2, min((int)nums2.size(), k)); for (int i=0; i<=min(k, (int)nums1.size()); i++){ if (k-i<=min(k,(int)nums2.size())) { vector<int> tem=merge(maxNumbers1[(int)maxNumbers1.size()-i-1], maxNumbers2[(int)maxNumbers2.size()-k+i-1]); if (less_than(result, tem)) result=tem; } } return result; } bool less_than(vector<int>& Number1, vector<int>& Number2){ int i=0; while (i<Number1.size()){ if (Number1[i]<Number2[i]) return true; else if (Number1[i]>Number2[i]) return false; else i++; } return false; } vector<int> merge(vector<int>& Number1, vector<int>& Number2){ if (Number1.size()==0) return Number2; if (Number2.size()==0) return Number1; vector<int> result; int i1=0, i2=0; while (i1<Number1.size() || i2<Number2.size()){ if (i2==Number2.size()) { result.push_back(Number1[i1]); i1++; }else if (i1==Number1.size()){ result.push_back(Number2[i2]); i2++; } else if (Number1[i1]<Number2[i2]){ result.push_back(Number2[i2]); i2++; }else if (Number1[i1]>Number2[i2]){ result.push_back(Number1[i1]); i1++; }else { int k1=i1, k2=i2; while (k1<Number1.size() && k2<Number2.size() && Number1[k1]==Number2[k2]) {k1++; k2++;} if (k1==Number1.size() || (k2<Number2.size() && Number2[k2]>Number1[k1])) { result.push_back(Number2[i2]); i2++; }else { result.push_back(Number1[i1]); i1++; } } } return result; } vector<vector<int>> maxNumbers(vector<int>& nums1, int k){ vector<vector<int>> result; vector<int> Number (nums1.begin(), nums1.begin()+k); for (int i=k; i<nums1.size(); i++){ int j=0; while (j+1<k && Number[j]>=Number[j+1]) j++; if (j==k-1){ if (nums1[i]>Number[j]) Number[j]=nums1[i]; } else { Number.erase(Number.begin()+j); Number.push_back(nums1[i]); } } result.push_back(Number); for (int i=0; i<k; i++){ int j=0; while (j+1<Number.size() && Number[j]>=Number[j+1]) j++; Number.erase(Number.begin()+j); result.push_back(Number); } return result; } };
Problem solution in C.
void getMaxNumber(int *nums, int size, int outsize, int *out) { int len = 0, i, k = size - outsize; out[0] = nums[0]; for (i = 1; i < size; i++) { while (len >= 0 && k > 0 && nums[i] > out[len]) k--, len--; out[++len] = nums[i]; } } int compareArr(int* nums1, int nums1Size, int* nums2, int nums2Size) { int i; for (i = 0; i < nums1Size && i < nums2Size && nums1[i] == nums2[i]; i++); //if (i == nums1Size && i == nums2Size) return 0; if (i == nums1Size) return -1; if (i == nums2Size) return 1; return (nums1[i] - nums2[i]); } void merge(int* nums1, int nums1Size, int* nums2, int nums2Size, int *out) { int len = 0, i = 0, j = 0; while (i < nums1Size && j < nums2Size) { if (nums1[i] > nums2[j]) out[len++] = nums1[i++]; else if (nums1[i] < nums2[j]) out[len++] = nums2[j++]; else if (compareArr(nums1 + i, nums1Size - i, nums2 + j, nums2Size - j) >= 0) out[len++] = nums1[i++]; else out[len++] = nums2[j++]; } while (i < nums1Size) out[len++] = nums1[i++]; while (j < nums2Size) out[len++] = nums2[j++]; } int compare(int *arr1, int *arr2, int len) { int i = 0; for (; i < len && arr1[i] == arr2[i]; i++); if (i < len) return arr1[i] - arr2[i]; return 0; } int min(int x, int y) {return x <= y ? x: y;} int* maxNumber(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize) { int i = 0, j = 0; int *arr1, *arr2, *ans, *tmp; if (k <= 0) { *returnSize = 0; return NULL; } arr1 = malloc(sizeof(int) * (nums1Size + nums2Size)); arr2 = arr1 + nums1Size; ans = malloc(sizeof(int) * k); tmp = malloc(sizeof(int) * k); for (j = 0; j < k; j++) ans[j] = 0; for (i = min(k, nums1Size); i >= 0; i--) { j = k - i; if (j > nums2Size) break; if (i > 0) getMaxNumber(nums1, nums1Size, i, arr1); if (j > 0) getMaxNumber(nums2, nums2Size, j, arr2); merge(arr1, i, arr2, j, tmp); if (compare(tmp, ans, k) > 0) { for (j = 0; j < k; j++) ans[j] = tmp[j]; } } free(tmp); free(arr1); *returnSize = k; return ans; }
0 Comments