面试题：两个按递增顺序排列的整数数组 nums1 和 nums2合并到nums1中，并递增排序，只允许开辟常量空间！！ |
您所在的位置：网站首页 › 递增递减排序题 › 面试题：两个按递增顺序排列的整数数组 nums1 和 nums2合并到nums1中，并递增排序，只允许开辟常量空间！！ |
|
给你两个按递增顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你合并 nums2 到 nums1 中，使合并后的数组同样按 递增顺序 排列。【只允许开辟常量空间！！！】 示例 ： 输入：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] 。 方法一：直接合并后排序算法 最直观的方法是先将数组 nums2 放进数组nums1的尾部，然后直接对整个数组进行排序。 public class Solution1 { public static void main(String[] args) { int[] nums1 = new int[]{1, 2, 3, 0, 0, 0}; int[] nums2 = new int[]{2, 5, 6}; merge(nums1, 3, nums2, 3); System.out.println(Arrays.toString(nums1)); } public static void merge(int[] nums1, int m, int[] nums2, int n) { //for (int i = 0; i = 0 || p2 >= 0) { if (p1 == -1) { cur = nums2[p2--]; } else if (p2 == -1) { cur = nums1[p1--]; } else if (nums1[p1] > nums2[p2]) { cur = nums1[p1--]; } else { cur = nums2[p2--]; } nums1[tail--] = cur; } } }复杂度分析 时间复杂度：O(m+n)。 指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。空间复杂度：O(1)。 直接对数组nums1 原地修改，不需要额外空间。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |