快速排序、排序 API + 计数排序：求解《1051. 高度检查器》
2022-06-13 11:26:12
快速排序、排序 API + 计数排序，求解《1051. 高度检查器》
例题
1051. 高度检查器
学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
返回满足 heights[i] != expected[i] 的 下标数量 。
答案
快速排序
var heightChecker = function(heights) {
const n = heights.length, a = heights.slice()
let ans = 0
quickSort(a, 0, n - 1)
for (let i = 0; i < n; i++) if (heights[i] !== a[i]) ans++
return ans
};
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, 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++
}
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
}排序 API
function heightChecker(heights: number[]): number {
const a = heights.slice().sort((a, b) => a - b), n = a.length
let ans = 0
for (let i = 0; i < n; i++) {
if (a[i] !== heights[i]) ans++
}
return ans
};class Solution {
function heightChecker($heights) {
$a = $heights;
$n = count($heights);
$ans = 0;
usort($a, function ($a, $b) {
return $a > $b;
});
for ($i = 0; $i < $n; $i++) {
if ($heights[$i] != $a[$i]) $ans++;
}
return $ans;
}
}func heightChecker(heights []int) int {
a, n, ans := append([]int{}, heights...), len(heights), 0
sort.Ints(a)
for i := 0; i < n; i++ {
if a[i] != heights[i] {
ans++
}
}
return ans
}class Solution:
def heightChecker(self, heights: List[int]) -> int:
ans = 0
for a, b in zip(heights, sorted(heights)):
if a != b: ans += 1
return ansclass Solution {
public int heightChecker(int[] heights) {
int n = heights.length;
int[] a = new int[n];
System.arraycopy(heights, 0, a, 0, n);
Arrays.sort(a);
int ans = 0;
for (int i = 0; i < n; i++) {
if (heights[i] != a[i]) ans++;
}
return ans;
}
}计数排序
var heightChecker = function(heights) {
const maxHeight = _.max(heights), n = heights.length, m = new Uint8Array(maxHeight + 1)
for (let i = 0; i < n; i++) m[heights[i]]++
let index = ans = 0
for (let h = 1; h <= maxHeight; h++) {
for (let j = 0; j < m[h]; j++) {
if (heights[index] !== h) ans++
index++
}
}
return ans
};function heightChecker(heights: number[]): number {
const maxHeight = Math.max.apply(null, heights), m = new Uint8Array(maxHeight + 1), n = heights.length
for (let i = 0; i < n; i++) m[heights[i]]++
let index = 0, ans = 0
for (let h = 1; h <= maxHeight; h++) {
for (let i = 0; i < m[h]; i++) {
if (heights[index] !== h) ans++
index++
}
}
return ans
};class Solution {
function heightChecker($heights) {
$maxHeight = max($heights);
$m = array_fill(0, $maxHeight + 1, 0);
foreach ($heights as $h) $m[$h]++;
$index = $ans = 0;
for ($h = 1; $h <= $maxHeight; $h++) {
for ($i = 0; $i < $m[$h]; $i++) {
if ($heights[$index] !== $h) $ans++;
$index++;
}
}
return $ans;
}
}func heightChecker(heights []int) int {
maxHeight := 0
for _, h := range heights {
if h > maxHeight {
maxHeight = h
}
}
m, ans, index := make([]int, maxHeight + 1), 0, 0
for _, h := range heights {
m[h]++
}
for h := 1; h <= maxHeight; h++ {
for i := 0; i < m[h]; i++ {
if heights[index] != h {
ans++
}
index++
}
}
return ans
}class Solution:
def heightChecker(self, heights: List[int]) -> int:
maxHeight = max(heights)
m = [0] * (maxHeight + 1)
for h in heights: m[h] += 1
index, ans = 0, 0
for h in range(1, maxHeight + 1):
for i in range(0, m[h]):
if heights[index] != h: ans += 1
index += 1
return ansclass Solution {
public int heightChecker(int[] heights) {
int maxHeight = Arrays.stream(heights).max().getAsInt(), index = 0, ans = 0;
int[] m = new int[maxHeight + 1];
for (int h : heights) m[h]++;
for (int h = 1; h <= maxHeight; h++) {
for (int i = 0; i < m[h]; i++) {
if (heights[index] != h) ans++;
index++;
}
}
return ans;
}
}