顺序遍历，三路划分（三切分 / 三指针 / 三分查找）的快速选择，虚地址：求解《280. 摆动排序》和《324. 摆动排序 II》

代码数据结构:数组查找:快速选择语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:C 语言:C++语言:C#语言:TypeScript 语言:Java

2022-06-28 19:37:13

顺序遍历，三路划分（三切分 / 三指针 / 三分查找）的快速选择，虚地址，求解《280. 摆动排序》和《324. 摆动排序 II》

C++ 的 nth_element

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); // 升序排序

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); // 自定义排序

例题

280. 摆动排序

给你一个的整数数组 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]);
      }
    }
  }
};

324. 摆动排序 II

给你一个整数数组 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);
  }
};

小宇

Github　力扣　 M站　全部原创，请勿转载

二分查找：求解《33. 搜索旋转排序数组》和《153. 寻找旋转排序数组中的最小值》

二分查找，求解《33. 搜索旋转排序数组》

快速排序、排序 API + 计数排序：求解《1051. 高度检查器》

快速排序、排序 API + 计数排序，求解《1051. 高度检查器》

回溯 + 动态规划（掩码 · 状态压缩）：2 方法求解《473. 火柴拼正方形》

回溯 + 动态规划（掩码 · 状态压缩），2 方法求解《473. 火柴拼正方形》