280. Wiggle Sort

最后更新

二刷

這個題做得真蠢。上來想的復雜了，想的是quick sort之類的，然后一個一個交換。

實際上直接交換就行。。沒啥特別的。

回頭看一刷也是同樣的思考過程= =宿命論啊。。

Time: O(n)
Space: O(1)

public class Solution {public void wiggleSort(int[] nums) {if (nums.length <= 1) return;for (int i = 1; i < nums.length; i++) {if (i % 2 == 0 && nums[i] > nums[i-1]) {swap(i, i-1, nums);} else if (i % 2 != 0 && nums[i] < nums[i-1]) {swap(i, i-1, nums);}}return;}public void swap(int l, int r, int[] nums) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;}
}

---

一刷

這個題一開始蠢了，先SORT了一下，然后IN-PLACE做了半天。。

發現直接greedy就可以。。。。。。

public class Solution {public void wiggleSort(int[] nums) {if(nums.length<=1) return;for(int i = 0; i < nums.length-1;i++){if(i%2==0){if(nums[i] > nums[i+1]){swap(nums,i,i+1);}}else{if(nums[i] < nums[i+1]){swap(nums,i,i+1);}}}}public void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}