回答編集履歴
1
コードの改善
answer
CHANGED
|
@@ -17,4 +17,40 @@
|
|
|
17
17
|
nums[i] > nums[j]については要素の比較なのでわかるのですが、i > midの存在意義がいまいちピンときていません。
|
|
18
18
|
|
|
19
19
|
i > mid の場合、l から mid までの配列要素は全部 tmp に入れてしまったということです。
|
|
20
|
-
したがって、nums[i] > nums[j] の比較をせずに tmp に nums[j] を入れてよいということです。
|
|
20
|
+
したがって、nums[i] > nums[j] の比較をせずに tmp に nums[j] を入れてよいということです。
|
|
21
|
+
|
|
22
|
+
**追記**
|
|
23
|
+
tmp を何度も new するのは無駄だし、
|
|
24
|
+
merge の wihleループで、`i <= mid`、`j <= r`、`i > mid`、`j <= r` の
|
|
25
|
+
比較を行うのも効率が悪いので書き直してみました。
|
|
26
|
+
```Java
|
|
27
|
+
class Solution {
|
|
28
|
+
int[] tmp;
|
|
29
|
+
|
|
30
|
+
public void sortArray(int[] nums) {
|
|
31
|
+
tmp = new int[nums.length];
|
|
32
|
+
mergeSort(nums, 0, nums.length - 1);
|
|
33
|
+
}
|
|
34
|
+
private void mergeSort(int[] nums, int l, int r) {
|
|
35
|
+
if (l >= r) return;
|
|
36
|
+
int mid = l + (r - l) / 2;
|
|
37
|
+
mergeSort(nums, l, mid);
|
|
38
|
+
mergeSort(nums, mid + 1, r);
|
|
39
|
+
merge(nums, l, mid, r);
|
|
40
|
+
}
|
|
41
|
+
private void merge(int[] nums, int l, int mid, int r) {
|
|
42
|
+
System.arraycopy(nums, l, tmp, l, mid - l + 1);
|
|
43
|
+
for (int i = mid + 1, k = r; i <= r; )
|
|
44
|
+
tmp[k--] = nums[i++];
|
|
45
|
+
for (int i = l, j = r, k = l; i <= j; )
|
|
46
|
+
nums[k++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j--];
|
|
47
|
+
}
|
|
48
|
+
|
|
49
|
+
public static void main(String[] args) {
|
|
50
|
+
int[] nums = { 5, 1, 1, 2, 0, 0 };
|
|
51
|
+
Solution sol = new Solution();
|
|
52
|
+
sol.sortArray(nums);
|
|
53
|
+
System.out.println(java.util.Arrays.toString(nums));
|
|
54
|
+
}
|
|
55
|
+
}
|
|
56
|
+
```
|