資訊專欄INFORMATION COLUMN
摘要：如果沒復(fù)雜度的要求，先也可以，再交叉放入數(shù)字也可以。交叉的時(shí)候注意是按照，降序的。
Wiggle Sort
題目鏈接：https://leetcode.com/problems...
這道題允許等號(hào)，相對(duì)簡單，有兩種方法：1. sort然后交換奇數(shù)位和它下一位的元素，2. 不滿足條件的時(shí)候直接交換
可以用遞推來說明一下這么做的正確性：
假設(shè)到第i位之前都滿足題目要求的關(guān)系
現(xiàn)在比較第i位和第i+1位
if i == odd:
nums[i] >= nums[i+1]，到i+1位都滿足條件
nums[i] < nums[i+1]，swap(i, i+1)，新的nums[i] >= nums[i+1] >= nums[i-1]，所以到i+1都滿足條件
if i == even:
同理
一直遞推到len(nums)，所以整個(gè)數(shù)組都滿足條件
public class Solution {
public void wiggleSort(int[] nums) {
/* condition: nums[odd] >= nums[even]
* 1. sort => [1, 2, 3, 4, 5, 6] => swap(i, i+1)
* 2. swap if a. nums[i] < nums[i+1] i = odd
* b. nums[i] > nums[i+1] i = even
*/
for(int i = 0; i < nums.length - 1; i++) {
if(i % 2 == 1 && nums[i] < nums[i+1]) swap(nums, i, i+1);
if(i % 2 == 0 && nums[i] > nums[i+1]) swap(nums, i, i+1);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
324. Wiggle Sort II
題目鏈接：https://leetcode.com/problems...
這題不能有等號(hào)，而且要求O(N)的時(shí)間和O(1)的空間，那么感覺只能quick select了。如果沒復(fù)雜度的要求，先sort也可以，再交叉放入數(shù)字也可以。交叉的時(shí)候注意是按照[2, 0, 3, 1]，降序的。
public class Solution {
public void wiggleSort(int[] nums) {
/* quick select: find the middle element
* 3 way partitions: [h, l, ...]
* [2, 0, 3, 1], [2, 0, 3, 1, 4]
*/
n = nums.length;
int mid = quickSelect(nums, 0, nums.length - 1, nums.length / 2);
partition(nums, 0, nums.length - 1, mid);
}
int n;
private void partition(int[] nums, int l, int r, int mid) {
int i = l;
while(i <= r) {
if(nums[mapping(i)] > mid) swap(nums, mapping(i++), mapping(l++));
else if(nums[mapping(i)] < mid) swap(nums, mapping(i), mapping(r--));
else i++;
}
}
private int mapping(int i) {
return (2 * i + 1) % (n | 1);
}
private int quickSelect(int[] nums, int l, int r, int k) {
if(l >= r) return nums[l];
int pivot = nums[r];
int index = l;
for(int i = l; i < r; i++) {
if(nums[i] < pivot) swap(nums, i, index++);
}
// swap the pivot to the correct position
swap(nums, index, r);
if(index == k) return nums[index];
else if(index < k) return quickSelect(nums, index + 1, r, k);
else return quickSelect(nums, l, index - 1, k);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66552.html
摘要：每隔兩位交換一次，如，處理為。難點(diǎn)是會(huì)有相等的元素，而要求相鄰元素除了外，不能相等。那么就不能取排序后相鄰的元素交換，而要和后面的元素交換。例如犧牲空間的做法是，建立一個(gè)新數(shù)組，按照我們想要的規(guī)律放入元素，最后回原數(shù)組。 Wiggle Sort Problem Given an unsorted array nums, reorder it in-place such that num...
摘要：就能滿足題目要求。代碼先將數(shù)組排序?qū)?shù)組中一對(duì)一對(duì)交換交換法復(fù)雜度時(shí)間空間思路題目對(duì)搖擺排序的定義有兩部分如果是奇數(shù)，如果是偶數(shù)，所以我們只要遍歷一遍數(shù)組，把不符合的情況交換一下就行了。 Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] = nums[i ...
Problem Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { ...
摘要：思路這道題就是要找區(qū)間之間是否有。而的復(fù)雜度是，所以最后總的復(fù)雜度為。思路的條件依然是不同的是這題需要求房間數(shù)。還是先，指向之前有的最小的那一個(gè)。接著的是，比小，所以又放入。。的是，比大，因此出，放入。。 Meeting Rooms Given an array of meeting time intervals consisting of start and end times [[...
H-Index 題目鏈接：https://leetcode.com/problems... sort： public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; // sort ...
閱讀 1889·2021-09-22 15:45
閱讀 1674·2019-08-30 15:55
閱讀 1856·2019-08-29 11:16
閱讀 3329·2019-08-26 11:44
閱讀 739·2019-08-23 17:58
閱讀 2719·2019-08-23 12:25
閱讀 1654·2019-08-22 17:15
閱讀 3643·2019-08-22 16:09
