成都网站建设企业,金融类网站设计,怎么把网站关联到万网,商业网点建设中心网站题目#xff1a;
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2#xff0c;另有两个整数 m 和 n #xff0c;分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中#xff0c;使合并后的数组同样按 非递减顺序 排列。
注意#xff1a;最终
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。
示例 2
输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3
输入nums1 [0], m 0, nums2 [1], n 1
输出[1]
解释需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-109 nums1[i], nums2[j] 109
解决
解法1利用Arrays中的sort方法排序直接求解
public void merge(int[] nums1,int m,int[] nums2,int n) {for(int i0;in;i){nums1[mi]nums2[i];}Arrays.sort(nums1);}
快速排序时间复杂度为O((mn)log(mn))。代码效率不是特别高。其最大的问题是题目给的数组元素本来是有序的但这样混起来之后用sort排序相当于又重新排序了一遍即没有充分利用元素的有序性。 解法2用双指针
每次从两个数组的头部各取出一个数比较把比较小的结果复制到临时数组中再把比较小数所在数组指针后移一位。把两个数组元素都复制到临时数组后临时数组的结果就是排序以后的结果了。再把临时数组的元素复制到nums1。这样的话两个数组都只循环了一遍时间复杂度为O(mn)。空间复杂度也是Omn)。
public void merge(int[] nums1,int m,int[] nums2,int n) {int kmn;int[] tempnew int[k];for(int index0,nums1Index0,nums2Index0;indexk;index){if(nums1Indexm) {//nums1数组已经取完接下来完全取nums2数组的值temp[index]nums2[nums2Index];}else if(nums2Indexn){temp[index]nums1[nums1Index];}else if(nums1[nums1Index]nums2[nums2Index]){//nums1数组元素值小于nums2数组元素值取nums1数组的值temp[index]nums1[nums1Index];}else{temp[index]nums2[nums2Index];}}for(int i0;ik;i){nums1[i]temp[i];}} 解法3用双指针倒序处理
把nums2的最后一个元素与nums1的有效的最后一个元素比较把大的放在nums1的最后一个0的位置。再把刚才的指针往前移一位再比较这样就用到nums1的空间了不用引入临时数组。这样时间复杂度为O(mn)空间复杂度为O(m)。 public void merge(int[] nums1,int m,int[] nums2,int n) {int kmn;for(int indexk-1,nums1Indexm-1,nums2Indexn-1;index0;index--){if(nums1Index0) {//nums1数组已经取完接下来完全取nums2数组的值nums1[index]nums2[nums2Index--];}else if(nums2Index0){break;}else if(nums1[nums1Index]nums2[nums2Index]){//nums1数组元素值大于nums2数组元素值取nums1数组的值nums1[index]nums1[nums1Index--];}else{nums1[index]nums2[nums2Index--];}}} 加油加油^_^
