const quickSelect= (nums, start, end, k) => { // 快速选择
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const quickSort = (nums, start, end) => { // 快速排序
if (start >= end) return
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
quickSort(nums, l + 1, end)
quickSort (nums, start, l - 1)
}
const swap = (nums, a, b) => { // 交换变量
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
固定选择基准元素:当数组完全升序或降序,每次都选择 最小值 或 最大值,快排速度减慢
为保证基准元素选取的随机性:可以先打乱数组
shuffle(array &$array): bool
API:从 7.1 起,由伪随机数改为 梅森旋转算法(Mersenne twister)const shuffle = nums => { // 用 Fisher-Yates shuffle 洗牌算法
let i = nums.length
while (i--) swap(nums, i, Math.random() * i | 0)
}
为保证基准元素选取的随机性:在 [start, end] 随机选取元素,与开始元素交换
const i = start + Math.floor(Math.random()*(end - start + 1)) // 随机选取元素
swap(nums, start, i) // 与开始元素交换
const quickSelect = (nums, start, end, k) => { // 快速选择
swap(nums, start, start + Math.random() * (end - start + 1) | 0) // 随机选取元素与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const quickSort = (nums, start, end) => { // 快速排序
if (start >= end) return
swap(nums, start, start + Math.random() * (end - start + 1) | 0) // 随机选取元素与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
quickSort(nums, l + 1, end)
quickSort(nums, start, l - 1)
}
为保证基准元素选取的随机性:取中间数,与开始元素交换
swap(nums, start, start + end >> 1)
const quickSelect = (nums, start, end, k) => { // 快速选择
swap(nums, start, start + end >> 1) // 取中间数与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const quickSort = (nums, start, end) => { // 快速排序
if (start >= end) return
swap(nums, start, start + end >> 1) // 取中间数与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
quickSort(nums, l + 1, end)
quickSort(nums, start, l - 1)
}
为保证基准元素选取的随机性:取中位数,与开始元素交换
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数
const quickSelect = (nums, start, end, k) => { // 快速选择
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const quickSort = (nums, start, end) => { // 快速排序
if (start >= end) return
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数与开始元素交换
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
quickSort(nums, l + 1, end)
quickSort(nums, start, l - 1)
}
新增一个指针,选择等于基准值的元素 减少重复元素的交换
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 quickSort = (nums, start, end) => { // 快速排序
if (start >= end) return
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const q = nums[start]
let l = start, i = start + 1, r = end
while (i <= r) {
if (nums[i] > q) swap(nums, i, r--)
else if (nums[i] < q) swap(nums, i++, l++)
else i++
}
quickSort(nums, l + 1, end)
quickSort (nums, start, l - 1)
}
给你一个长度为 n 的整数数组 nums ,返回使所有数组元素相等需要的最少移动数。
在一步操作中,你可以使数组中的一个元素加 1 或者减 1 。
var minMoves2 = function(nums) {
const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
let r = 0
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};
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 minMoves2(nums: number[]): number {
const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
let r = 0
for (let i = 0; i < n; i++) r += Math.abs(nums[i] - median)
return r
};
const quickSelect = (nums: number[], start: number, end: number, k: number) => {
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: number[], a: number, b: number) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
func minMoves2(nums []int) int {
n := len(nums)
median, r := quickSelect(nums, 0, n - 1, n >> 1), 0
for _, num := range nums {
r += int(math.Abs(float64(num - median)))
}
return r
}
func quickSelect(nums []int, start int, end int, k int) int {
swap(nums, start, (start + end + (start + end) >> 1) / 3 | 0)
l, i, r, pivot := start, start + 1, end, nums[start]
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]
} else if l < k {
return quickSelect(nums, l + 1, end, k)
} else {
return quickSelect(nums, start, l - 1, k)
}
}
func swap(nums []int, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}
class Solution {
function minMoves2($nums) {
$n = count($nums);
$median = $this->quickSelect($nums, 0, $n - 1, $n >> 1);
$r = 0;
foreach ($nums as $num) $r += abs($num - $median);
return $r;
}
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--);
else if ($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) {
list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
}
}
class Solution:
def minMoves2(self, nums: List[int]) -> int:
def swap(nums, a, b):
nums[a], nums[b] = nums[b], nums[a]
def quickSelect(nums, start, end, k):
swap(nums, start, int((start + end + (start + end >> 1)) / 3))
pivot, l, i, r = nums[start], start, start + 1, end
while i <= r:
if nums[i] > pivot:
swap(nums, i, r)
r -= 1
elif nums[i] < pivot:
swap(nums, i, l)
i += 1
l += 1
else:
i += 1
if l == k: return nums[l]
return quickSelect(nums, l + 1, end, k) if l < k else quickSelect(nums, start, l - 1, k)
n, r = len(nums), 0
median = quickSelect(nums, 0, n - 1, n >> 1)
for num in nums: r += abs(num - median)
return r
class Solution {
public int minMoves2(int[] nums) {
int n = nums.length;
int median = quickSelect(nums, 0, n - 1, n >> 1);
int r = 0;
for (int num : nums) r += Math.abs(num - median);
return r;
}
private int quickSelect(int[] nums, int start, int end, int k) {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0);
int pivot = nums[start];
int l = start;
int i = start + 1;
int 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);
}
private void swap(int[] nums, int a, int b) {
nums[a] = nums[b] + (nums[b] = nums[a]) * 0;
}
}
/**
* @param {number[]} nums
* @return {number}
*/
var minMoves2 = function(nums) {
const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
let r = 0
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};
const quickSelect= (nums, start, end, k) => { // 快速选择
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
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 minMoves2(nums: number[]): number {
const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
let r = 0
for (let i = 0; i < n; i++) r += Math.abs(nums[i] - median)
return r
};
const quickSelect = (nums: number[], start: number, end: number, k: number) => {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start, r = end
while (l < r) {
while (l < r && nums[r] >= pivot) r--
while (l < r && nums[l] <= pivot) l++
swap(nums, l, r)
}
swap(nums, l, start)
if (l === k) return nums[l]
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums: number[], a: number, b: number) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}
func minMoves2(nums []int) int {
n := len(nums)
median, r := quickSelect(nums, 0, n - 1, n >> 1), 0
for _, num := range nums {
r += int(math.Abs(float64(num - median)))
}
return r
}
func quickSelect(nums []int, start int, end int, k int) int {
swap(nums, start, (start + end + (start + end) >> 1) / 3 | 0)
l, r, pivot := start, end, nums[start]
for l < r {
for l < r && nums[r] >= pivot {
r--
}
for l < r && nums[l] <= pivot {
l++
}
swap(nums, l, r)
}
swap(nums, l, start)
if l == k {
return nums[l]
} else if l < k {
return quickSelect(nums, l + 1, end, k)
} else {
return quickSelect(nums, start, l - 1, k)
}
}
func swap(nums []int, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}
class Solution {
function minMoves2($nums) {
$n = count($nums);
$median = $this->quickSelect($nums, 0, $n - 1, $n >> 1);
$r = 0;
foreach ($nums as $num) $r += abs($num - $median);
return $r;
}
function quickSelect(&$nums, $start, $end, $k) {
$this->swap($nums, $start, ($start + $end + ($start + $end >> 1)) / 3 | 0);
$pivot = $nums[$start];
$l = $start;
$r = $end;
while ($l < $r) {
while ($l < $r && $nums[$r] >= $pivot) $r--;
while ($l < $r && $nums[$l] <= $pivot) $l++;
$this->swap($nums, $l, $r);
}
$this->swap($nums, $l, $start);
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) {
list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
}
}
class Solution:
def minMoves2(self, nums: List[int]) -> int:
def swap(nums, a, b):
nums[a], nums[b] = nums[b], nums[a]
def quickSelect(nums, start, end, k):
swap(nums, start, int((start + end + (start + end >> 1)) / 3))
pivot, l, r = nums[start], start, end
while l < r:
while l < r and nums[r] >= pivot: r -= 1
while l < r and nums[l] <= pivot: l += 1
swap(nums, l, r)
swap(nums, l, start)
if l == k: return nums[l]
return quickSelect(nums, l + 1, end, k) if l < k else quickSelect(nums, start, l - 1, k)
n, r = len(nums), 0
median = quickSelect(nums, 0, n - 1, n >> 1)
for num in nums: r += abs(num - median)
return r
class Solution {
public int minMoves2(int[] nums) {
int n = nums.length;
int median = quickSelect(nums, 0, n - 1, n >> 1);
int r = 0;
for (int num : nums) r += Math.abs(num - median);
return r;
}
private int quickSelect(int[] nums, int start, int end, int k) {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0);
int pivot = nums[start];
int l = start;
int r = end;
while (l < r) {
while (l < r && nums[r] >= pivot) r--;
while (l < r && nums[l] <= pivot) l++;
swap(nums, l, r);
}
swap(nums, l, start);
if (l == k) return nums[l];
return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
}
private void swap(int[] nums, int a, int b) {
nums[a] = nums[b] + (nums[b] = nums[a]) * 0;
}
}
var minMoves2 = function(nums) {
nums.sort((a, b) => a - b)
const n = nums.length, median = n & 1 ? nums[n >> 1] : (nums[n >> 1] + nums[(n >> 1) - 1]) >> 1
let r = 0
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};
function minMoves2(nums: number[]): number {
nums.sort((a, b) => a - b)
const n = nums.length, median = n & 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1
let r = 0;
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};
func minMoves2(nums []int) int {
sort.Ints(nums)
n, r, median := len(nums), 0, 0
if n & 1 == 1 {
median = nums[n >> 1]
} else {
median = (nums[n >> 1] + nums[n >> 1 - 1]) >> 1
}
for _, num := range nums {
r += int(math.Abs(float64(num - median)))
}
return r
}
class Solution {
function minMoves2($nums) {
usort($nums, function($a, $b) {
return $a > $b;
});
$n = count($nums);
$median = $n & 1 ? $nums[$n >> 1] : $nums[$n >> 1] + $nums[($n >> 1) - 1] >> 1;
$r = 0;
foreach($nums AS $num) {
$r += abs($num - $median);
}
return $r;
}
}
class Solution:
def minMoves2(self, nums: List[int]) -> int:
nums.sort()
n, r = len(nums), 0
median = nums[n >> 1] if n & 1 else nums[n >> 1] + nums[(n >> 1) - 1] >> 1
for num in nums:
r += abs(num - median)
return r
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int median = (n & 1) == 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1;
int r = 0;
for (int num : nums) {
r += Math.abs(num - median);
}
return r;
}
}