Merge Sorted Array
思路一: 比较两个数组前面最小值,依次插入到新数组中,最后复制新数组到 num1 中
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] result = new int[nums1.length];
int i = 0;
int x = 0;
int y = 0;
int valY;
int valX;
while (i < nums1.length) {
if (y < n) {
valY = nums2[y];
} else {
valY = Integer.MAX_VALUE;
}
if (x < m) {
valX = nums1[x];
} else {
valX = Integer.MAX_VALUE;
}
if (valX < valY) {
x++;
result[i] = valX;
} else {
y++;
result[i] = valY;
}
i++;
}
for (i = 0; i < result.length; i++) {
nums1[i] = result[i];
}
}
思路二: 从数组后面开始比较,可以在 nums1 数组上直接操作,比思路一少了额外的数组内存申请
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = nums1.length - 1;
int x = m - 1;
int y = n - 1;
while (i >= 0) {
if (x < 0 || y < 0) break;
if (nums1[x] > nums2[y]) {
nums1[i--] = nums1[x--];
} else {
nums1[i--] = nums2[y--];
}
}
while (x >= 0 && i >= 0) {
nums1[i--] = nums1[x--];
}
while (y >= 0 && i >= 0) {
nums1[i--] = nums2[y--];
}
}
标签:int,valY,nums1,--,88,result,easy,leetcode,nums2
From: https://www.cnblogs.com/iyiluo/p/16789177.html