回答編集履歴
1
コードの改善
test
CHANGED
|
@@ -37,3 +37,75 @@
|
|
|
37
37
|
i > mid の場合、l から mid までの配列要素は全部 tmp に入れてしまったということです。
|
|
38
38
|
|
|
39
39
|
したがって、nums[i] > nums[j] の比較をせずに tmp に nums[j] を入れてよいということです。
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
**追記**
|
|
44
|
+
|
|
45
|
+
tmp を何度も new するのは無駄だし、
|
|
46
|
+
|
|
47
|
+
merge の wihleループで、`i <= mid`、`j <= r`、`i > mid`、`j <= r` の
|
|
48
|
+
|
|
49
|
+
比較を行うのも効率が悪いので書き直してみました。
|
|
50
|
+
|
|
51
|
+
```Java
|
|
52
|
+
|
|
53
|
+
class Solution {
|
|
54
|
+
|
|
55
|
+
int[] tmp;
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
public void sortArray(int[] nums) {
|
|
60
|
+
|
|
61
|
+
tmp = new int[nums.length];
|
|
62
|
+
|
|
63
|
+
mergeSort(nums, 0, nums.length - 1);
|
|
64
|
+
|
|
65
|
+
}
|
|
66
|
+
|
|
67
|
+
private void mergeSort(int[] nums, int l, int r) {
|
|
68
|
+
|
|
69
|
+
if (l >= r) return;
|
|
70
|
+
|
|
71
|
+
int mid = l + (r - l) / 2;
|
|
72
|
+
|
|
73
|
+
mergeSort(nums, l, mid);
|
|
74
|
+
|
|
75
|
+
mergeSort(nums, mid + 1, r);
|
|
76
|
+
|
|
77
|
+
merge(nums, l, mid, r);
|
|
78
|
+
|
|
79
|
+
}
|
|
80
|
+
|
|
81
|
+
private void merge(int[] nums, int l, int mid, int r) {
|
|
82
|
+
|
|
83
|
+
System.arraycopy(nums, l, tmp, l, mid - l + 1);
|
|
84
|
+
|
|
85
|
+
for (int i = mid + 1, k = r; i <= r; )
|
|
86
|
+
|
|
87
|
+
tmp[k--] = nums[i++];
|
|
88
|
+
|
|
89
|
+
for (int i = l, j = r, k = l; i <= j; )
|
|
90
|
+
|
|
91
|
+
nums[k++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j--];
|
|
92
|
+
|
|
93
|
+
}
|
|
94
|
+
|
|
95
|
+
|
|
96
|
+
|
|
97
|
+
public static void main(String[] args) {
|
|
98
|
+
|
|
99
|
+
int[] nums = { 5, 1, 1, 2, 0, 0 };
|
|
100
|
+
|
|
101
|
+
Solution sol = new Solution();
|
|
102
|
+
|
|
103
|
+
sol.sortArray(nums);
|
|
104
|
+
|
|
105
|
+
System.out.println(java.util.Arrays.toString(nums));
|
|
106
|
+
|
|
107
|
+
}
|
|
108
|
+
|
|
109
|
+
}
|
|
110
|
+
|
|
111
|
+
```
|