var maxNumber = function (nums1, nums2, k) { var res = newArray(k).fill(0), tmp; var len1 = nums1.length, len2 = nums2.length; //extract i elements from nums1 and extract k-i elements form nums2,then merge and compare for (var i = Math.max(0, k - len2); i <= Math.min(len1, k); i++) { tmp = mergeArray(getMax(nums1, i), getMax(nums2, k - i)); if (isGreater(tmp, res, 0, 0)) res = tmp; }
return res; };
//compre the two arrays from index i and j var isGreater = function (nums1, nums2, i, j) { while (i >= 0 && i < nums1.length && j >= 0 && j < nums2.length && nums1[i] == nums2[j]) { i++; j++; } return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]); };
//put the max in front of the merged array var mergeArray = function (nums1, nums2) { var merge = []; var i = 0, j = 0; while (i < nums1.length && j < nums2.length) { if (isGreater(nums1, nums2, i, j)) { merge.push(nums1[i++]); } else { merge.push(nums2[j++]); } } for (; i < nums1.length; i++) merge.push(nums1[i]); for (; j < nums2.length; j++) merge.push(nums2[j]); return merge; };
//get k max number preserving the order of the merged array var getMax = function (num, k) { var len = num.length; var i = 0, j = 0, maxArray = newArray(k); while (i < num.length) { while (j > 0 && len - i + j > k && num[i] > maxArray[j - 1]) { j--; } if (j < k) maxArray[j++] = num[i]; i++; } return maxArray; };
var findSmallestPermutation = function (permutations) { var len = permutations.length; var res = newArray(len + 1).fill(0); res.forEach(function (item, index, array) { array[index] = index + 1; }); var start = 0, end = 0; while (start < len) { while (permutations[end] == 'D') { end++; } if (end > start) reverse(res, start, end); start = end = end + 1; } return res; };
var reverse = function (nums, start, end) { var tmp; while (start < end) { tmp = nums[start]; nums[start++] = nums[end]; nums[end--] = tmp; } };