1,参照归并排序
可以参照归并排序,具体可以看下《排序-归并排序》
public void merge(int[] nums1, int m, int[] nums2, int n) { int temp[] = new int[m + n]; int index = 0; int i = 0; int j = 0; while (i < m && j < n) { if (nums1[i] <= nums2[j]) temp[index++] = nums1[i++]; else temp[index++] = nums2[j++]; } for (; i < m; ) { temp[index++] = nums1[i++]; } for (; j < n; ) { temp[index++] = nums2[j++]; } //再把数组temp中的值赋给nums1 for (int k = 0; k < m + n; k++) { nums1[k] = temp[k]; } }
2,解法二
题目说nums1有足够的空间容纳nums2,所以我们可以认为nums1的长度肯定大于nums2。
正常的归并都是从小往大开始,这里我们可以换种思路,从大往小开始。由于牛客网目前不支持视频,我把它转为gif图了,稍微有点卡顿,可以看下
再来看下代码
public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int end = m + n - 1; while (j >= 0) { nums1[end--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--]; } }
3,使用官方api
或者还可以这样写
public void merge(int[] nums1, int m, int[] nums2, int n) { System.arraycopy(nums2, 0, nums1, m, n); Arrays.sort(nums1); }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666