Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….
Example
No.1
Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].
No.2
Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].
Note
You may assume all input has valid answer.
Follow Up
Can you do it in O(n) time and/or in-place with O(1) extra space?
O(nlogn) runtime, O(n) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public void (int[] nums) {
int[] copy = nums.clone();
Arrays.sort(copy);
int left = (copy.length - 1) >> 1;
int right = copy.length - 1;
int idx = 0;
while (left >= 0 && right >= (copy.length + 1) >> 1) {
nums[idx++] = copy[left--];
nums[idx++] = copy[right--];
}
if (left == 0)
nums[idx] = copy[0];
}
|
O(n) runtime, O(1) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
public void (int[] nums) {
int n = nums.length;
int lo = 0;
int hi = n - 1;
int midNum = partition(nums, lo, hi, (n - 1) >> 1);
for (int i = 0; i <= hi;) {
if (nums[getMapIdx(i, n)] > midNum)
swap(nums, getMapIdx(i++, n) , getMapIdx(lo++, n));
else if (nums[getMapIdx(i, n)] < midNum)
swap(nums, getMapIdx(i, n), getMapIdx(hi--, n));
else
i++;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int getMapIdx(int i, int n) {
return (2 * i + 1) % (n | 1);
}
private int partition(int[] nums, int lo, int hi, int k) {
int left = lo;
int right = hi;
int num = nums[lo];
while (left < right) {
while (left < right && nums[right] >= num)
right--;
while (left < right && nums[left] <= num)
left++;
swap(nums, left, right);
}
swap(nums, lo, left);
if (left - lo == k)
return num;
else if (left - lo < k)
return partition(nums, left + 1, hi, k - (left - lo + 1));
else
return partition(nums, lo, right - 1, k);
}
|
近期评论