leetcode/code/lc324.java at master · mJackie/leetcode · GitHub

History

58 lines (52 loc) · 1.9 KB

Raw

package code;

import java.util.Arrays;

* 324. Wiggle Sort II

* 题意：小大小大小大这样排序

* 难度：Medium

* 分类：Sort

* 思路：先找到中位数，然后一个小于中位数的，一个大于中位数的这样组合

* 用 index map 的方式可以使空间也为O(1)

* Tips：挺难的。

public class lc324 {

public void wiggleSort(int[] nums) {

if(nums.length==1) return;

int n = nums.length, m = (n + 1) >> 1;// (nums.length+1)/2 注意+1

int[] copy = Arrays.copyOf(nums, n);

int median = findMedium(nums, 0, nums.length-1, m);

for (int i = 0, j = 0, k = n - 1; j <= k;) { // <medium的放左边， >在右边

if (copy[j] < median) {

swap(copy, j++, i++);

} else if (copy[j] > median) {

swap(copy, j, k--);

} else {

j++;

}

for (int i = m - 1, j = 0; i >= 0; i--, j += 2) nums[j] = copy[i]; //注意这点细节，i--倒着来，防止中位数重复的情况bug

for (int i = n - 1, j = 1; i >= m; i--, j += 2) nums[j] = copy[i];

}

private void swap(int[] nums, int i, int j) {

int t = nums[i];

nums[i] = nums[j];

nums[j] = t;

}

public int findMedium(int[] nums, int left, int right, int k){

int l = left;

int r = right;

while(left<right){

while( left<right && nums[right]>=nums[left] ) right--;

int temp = nums[left];

nums[left] = nums[right];

nums[right] = temp;

while( left<right && nums[left]<nums[right]) left++;

temp = nums[left];

nums[left] = nums[right];

nums[right] = temp;

}

if(left==k-1) return nums[left];

else if(left>=k) return findMedium(nums, l, right-1, k);

else return findMedium(nums, right+1, r, k);

}

leetcode/code/lc324.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc324.java

Latest commit

History

Breadcrumbs

lc324.java

File metadata and controls