February 8, 2016
Wiggle Sort
Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
Julia figured out the easy way to do it, O(n) time, O(1) space. So motivated. Next time, think about algorithm by yourself, start from brute force, and then, work towards requirement - efficient solution.
https://segmentfault.com/a/1190000003783283
public class Solution {
public void wiggleSort(int[] nums) {
for(int i = 1; i < nums.length; i++){
// 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1]
if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){
int tmp = nums[i-1];
nums[i-1] = nums[i];
nums[i] = tmp;
}
}
}
}
To be continued.
I'm not sure this is a correct answer. Try input with {4,3,2,2,1,0}. your code gives {3, 4, 2, 2, 0, 1}. Can you please clarify?
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThanks for asking. I noticed that the algorithm is for Wiggle Sort Algorithm, not Leetcode 324 Wiggle Sort II.
ReplyDelete