void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); // 升序排序
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); // 自定义排序
给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]...
输入数组总是有一个有效的答案。
示例 1:
输入:nums = [3,5,2,1,6,4]
输出:[3,5,1,6,2,4]
解释:[1,6,2,5,3,4]也是有效的答案
var wiggleSort = function(nums) {
const n = nums.length
for (let i = 0; i + 1 < n; i++) {
if ((i & 1) === 0) { // 偶数位
if (nums[i] > nums[i + 1]) swap(nums, i, i + 1)
} else { // 奇数位
if (nums[i] < nums[i + 1]) swap(nums, i, i + 1)
}
}
};
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
function wiggleSort(nums: number[]): void {
const n = nums.length
for (let i = 0; i + 1 < n; i++) {
if ((i & 1) === 0) {
if (nums[i] > nums[i + 1]) swap(nums, i, i + 1)
} else {
if (nums[i] < nums[i + 1]) swap(nums, i, i + 1)
}
}
};
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
func wiggleSort(nums []int) {
n := len(nums)
for i := 0; i + 1 < n; i++ {
if i & 1 == 0 {
if nums[i] > nums[i + 1] {
swap(nums, i, i + 1)
}
} else {
if nums[i] < nums[i + 1] {
swap(nums, i, i + 1)
}
}
}
}
func swap(nums []int, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}
class Solution {
function wiggleSort(&$nums) {
$n = count($nums);
for ($i = 0; $i + 1 < $n; $i++) {
if (($i & 1) === 0) {
if ($nums[$i] > $nums[$i + 1]) $this->swap($nums, $i, $i + 1);
} else {
if ($nums[$i] < $nums[$i + 1]) $this->swap($nums, $i, $i + 1);
}
}
}
function swap(&$nums, $a, $b) {
$t = $nums[$a];
$nums[$a] = $nums[$b];
$nums[$b] = $t;
}
}
class Solution:
def swap(self, nums: List[int], a: int, b: int) -> None:
nums[a], nums[b] = nums[b], nums[a]
def wiggleSort(self, nums: List[int]) -> None:
for i in range(0, len(nums) - 1):
if (i & 1) == 0:
if nums[i] > nums[i + 1]: self.swap(nums, i, i + 1)
else:
if nums[i] < nums[i + 1]: self.swap(nums, i, i + 1)
class Solution {
public void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
public void wiggleSort(int[] nums) {
int n = nums.length;
for (int i = 0; i + 1 < n; i++) {
if ((i & 1) == 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 class Solution {
public void WiggleSort(int[] nums) {
int n = nums.Length;
for (int i = 0; i + 1 < n; i++) {
if ((i & 1) == 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 a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}
void wiggleSort(int* nums, int numsSize){
for (int i = 0; i + 1 < numsSize; i++) {
if ((i & 1) == 0) {
if (nums[i] > nums[i + 1]) swap(&nums[i], &nums[i + 1]);
} else {
if (nums[i] < nums[i + 1]) swap(&nums[i], &nums[i + 1]);
}
}
}
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i + 1 < n; i++) {
if ((i & 1) == 0) {
if (nums[i] > nums[i + 1]) swap(nums[i], nums[i + 1]);
} else {
if (nums[i] < nums[i + 1]) swap(nums[i], nums[i + 1]);
}
}
}
};
给你一个整数数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1:
输入:nums = [1,5,1,1,6,4]
输出:[1,6,1,5,1,4]
解释:[1,4,1,5,1,6] 同样是符合题目要求的结果,可以被判题程序接受。
var wiggleSort = function(nums) {
nums.sort((a, b) => a - b)
const n = nums.length, t = new Uint16Array(n)
let l = n - 1 >> 1, r = n - 1
for (let i = 0; i < n; i++) {
t[i] = i & 1 ? nums[r--] : nums[l--];
}
for (let i = 0; i < n; i++) {
nums[i] = t[i]
}
};
var wiggleSort = function(nums) {
const n = nums.length
const median = quickSelect(nums, 0, n - 1, n >> 1)
const f = i => (i * 2 + 1) % (n | 1)
let l = i = 0, r = n - 1
while (i <= r) {
if (nums[f(i)] > median) swap(nums, f(i++), f(l++)) // 奇 <> 奇,奇得 大
else if (nums[f(i)] < median) swap(nums, f(i), f(r--)) // 奇 <> 偶,偶得 小
else i++
}
};
const quickSelect = (nums, start, end, k) => {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start , i = start + 1, r = end
while (i <= r) {
if (nums[i] > pivot) swap(nums, i, r--)
else if (nums[i] < pivot) swap(nums, i++, l++)
else i++
}
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
function wiggleSort(nums: number[]): void {
const n = nums.length
const median = quickSelect(nums, 0, n - 1, n >> 1)
const f = i => ((i << 1) + 1) % (n | 1)
let i = 0, l = 0, r = n - 1
while (i <= r) {
if (nums[f(i)] > median) swap(nums, f(i++), f(l++))
else if (nums[f(i)] < median) swap(nums, f(i), f(r--))
else i++
}
};
const quickSelect = (nums, start, end, k) => {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start , i = start + 1, r = end
while (i <= r) {
if (nums[i] > pivot) swap(nums, i, r--)
else if (nums[i] < pivot) swap(nums, i++, l++)
else i++
}
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
func f(i int, n int) int {
return (i << 1 + 1) % (n | 1)
}
func wiggleSort(nums []int) {
n := len(nums)
median := quickSelect(nums, 0, n - 1, n >> 1)
l, i, r := 0, 0, n - 1
for i <= r {
if nums[f(i, n)] > median {
swap(nums, f(i, n), f(l, n))
i++
l++
} else if nums[f(i, n)] < median {
swap(nums, f(i, n), f(r, n))
r--
} else {
i++
}
}
}
func quickSelect(nums []int , start, end, k int) int {
swap(nums, start, (start + end + ((start + end) >> 1)) / 3)
pivot := nums[start]
l, i, r := start, start + 1, end
for i <= r {
if nums[i] > pivot {
swap(nums, i, r)
r--
} else if nums[i] < pivot {
swap(nums, i, l)
i++
l++
} else {
i++
}
}
if l == k {
return nums[l]
}
if l < k {
return quickSelect(nums, l + 1, end, k)
}
return quickSelect(nums, start, l - 1, k)
}
func swap(nums []int, a, b int) {
nums[a], nums[b] = nums[b], nums[a]
}
class Solution {
function f($i, $n) {
return (($i << 1) + 1) % ($n | 1);
}
function wiggleSort(&$nums) {
$n = count($nums);
$median = $this->quickSelect($nums, 0, $n - 1, $n >> 1);
$l = 0;
$i = 0;
$r = $n - 1;
while ($i <= $r) {
if ($nums[$this->f($i, $n)] > $median) $this->swap($nums, $this->f($i++, $n), $this->f($l++, $n));
elseif ($nums[$this->f($i, $n)] < $median) $this->swap($nums, $this->f($i, $n), $this->f($r--, $n));
else $i++;
}
}
function quickSelect(&$nums, $start, $end, $k) {
$this->swap($nums, $start, ($start + $end + ($start + $end >> 1)) / 3 | 0);
$pivot = $nums[$start];
$l = $start;
$i = $start + 1;
$r = $end;
while ($i <= $r) {
if ($nums[$i] > $pivot) $this->swap($nums, $i, $r--);
elseif ($nums[$i] < $pivot) $this->swap($nums, $i++, $l++);
else $i++;
}
if ($l === $k) return $nums[$l];
return $l < $k ? $this->quickSelect($nums, $l + 1, $end, $k) : $this->quickSelect($nums, $start, $l - 1, $k);
}
function swap(&$nums, $a, $b) {
$t = $nums[$a];
$nums[$a] = $nums[$b];
$nums[$b] = $t;
}
}
class Solution:
def swap(self, nums: List[int], a: int, b: int) -> None:
nums[a], nums[b] = nums[b], nums[a]
def f(self, i: int, n: int) -> int:
return ((i << 1) + 1) % (n | 1)
def quickSelect(self, nums: List[int], start: int, end: int, k: int) -> int:
self.swap(nums, start, int((start + end + (start + end >> 1)) / 3))
pivot = nums[start]
l, i, r = start, start + 1, end
while i <= r:
if nums[i] > pivot:
self.swap(nums, i, r)
r -= 1
elif nums[i] < pivot:
self.swap(nums, i, l)
i += 1
l += 1
else: i += 1
if l == k: return nums[l]
return self.quickSelect(nums, l + 1, end, k) if l < k else self.quickSelect(nums, start, l - 1, k)
def wiggleSort(self, nums: List[int]) -> None:
n = len(nums)
median = self.quickSelect(nums, 0, n - 1, n >> 1)
l, i, r = 0, 0, n - 1
while i <= r:
if nums[self.f(i, n)] > median:
self.swap(nums, self.f(i, n), self.f(l, n))
i += 1
l += 1
elif nums[self.f(i, n)] < median:
self.swap(nums, self.f(i, n), self.f(r, n))
r -= 1
else: i += 1
class Solution {
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = quickSelect(nums, 0, n - 1, n >> 1);
int l = 0, i = 0, r = n - 1;
while (i <= r) {
if (nums[f(i, n)] > median) swap(nums, f(i++, n), f(l++, n));
else if (nums[f(i, n)] < median) swap(nums, f(i, n), f(r--, n));
else i++;
}
}
public int f(int i, int n) {
return ((i << 1) + 1) % (n | 1);
}
public int quickSelect(int[] nums, int start, int end, int k) {
swap(nums, start, (start + end + (start + end >> 1)) / 3);
int pivot = nums[start];
int l = start, i = start + 1, r = end;
while (i <= r) {
if (nums[i] > pivot) swap(nums, i, r--);
else if (nums[i] < pivot) swap(nums, i++, l++);
else i++;
}
if (l == k) return nums[l];
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
}
public void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}
public class Solution {
public int f(int i, int n) {
return ((i << 1) + 1) % (n | 1);
}
public void WiggleSort(int[] nums) {
int n = nums.Length;
int median = quickSelect(nums, 0, n - 1, n >> 1);
int l = 0, i = 0, r = n - 1;
while (i <= r) {
if (nums[f(i, n)] > median) swap(nums, f(i++, n), f(l++, n));
else if (nums[f(i, n)] < median) swap(nums, f(i, n), f(r--, n));
else i++;
}
}
public int quickSelect(int[] nums, int start, int end, int k) {
swap(nums, start, (start + end + (start + end >> 1)) / 3);
int pivot = nums[start];
int l = start, i = start + 1, r = end;
while (i <= r) {
if (nums[i] > pivot) swap(nums, i, r--);
else if (nums[i] < pivot) swap(nums, i++, l++);
else i++;
}
if (l == k) return nums[l];
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
}
public void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}
void swap(int* nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
int quickSelect(int* nums, int start, int end, int k) {
swap(nums, start, (start + end + ((start + end) >> 1)) / 3);
int pivot = nums[start];
int l = start, i = start + 1, r = end;
while (i <= r) {
if (nums[i] > pivot) swap(nums, i, r--);
else if (nums[i] < pivot) swap(nums, i++, l++);
else i++;
}
if (l == k) return nums[l];
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
}
int f(int i, int n) {
return ((i << 1) + 1) % (n | 1);
}
void wiggleSort(int* nums, int numsSize){
int median = quickSelect(nums, 0, numsSize - 1, numsSize >> 1);
int l = 0, i = 0, r = numsSize - 1;
while (i <= r) {
if (nums[f(i, numsSize)] > median) swap(nums, f(i++, numsSize), f(l++, numsSize));
else if (nums[f(i, numsSize)] < median) swap(nums, f(i, numsSize), f(r--, numsSize));
else i++;
}
}
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
int median = quickSelect(nums, 0, n - 1, n >> 1);
int i = 0, l = 0, r = n - 1;
while (i <= r) {
if (nums[f(i, n)] > median) swap(nums[f(i++, n)], nums[f(l++, n)]);
else if (nums[f(i, n)] < median) swap(nums[f(i, n)], nums[f(r--, n)]);
else i++;
}
}
int f(int i, int n) {
return ((i << 1) + 1) % (n | 1);
}
int quickSelect(vector<int>& nums, int start, int end, int k) {
swap(nums[start], nums[(start + end + ((start + end) >> 1)) / 3]);
int pivot = nums[start], n = nums.size();
int l = start, i = start + 1, r = end;
while (i <= r) {
if (nums[i] > pivot) swap(nums[i], nums[r--]);
else if (nums[i] < pivot) swap(nums[i++], nums[l++]);
else i++;
}
if (l == k) return nums[l];
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
}
};
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
int median = nums[n >> 1];
int l = 0, i = 0, r = n - 1;
while (i <= r) {
if (nums[f(i, n)] > median) swap(nums[f(i++, n)], nums[f(l++, n)]);
else if (nums[f(i, n)] < median) swap(nums[f(i, n)], nums[f(r--, n)]);
else i++;
}
}
int f(int i, int n) {
return ((i << 1) + 1) % (n | 1);
}
};