在排序数组中查找元素的第一个和最后一个位置、数组中的第K个最大元素和颜色分类

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例
1
输入: nums = [5,7,7,8,8,10], target = 8
2
输出: [3,4]
3
4
输入: nums = [5,7,7,8,8,10], target = 6
5
输出: [-1,-1]
Copied!

方法一 二分查找

思路
由于数组已经时升序排列,可直接根据二分查找,往左定位第一个位置,往右定位最后一个位置 二分查找的实现上可以使用循环或者递归。
详解
  1. 1.
    根据二分查找,找到左边第一个不小于目标值的位置
  2. 2.
    从上一步中的位置开始到最后,二分查找,确定右边最后一个符合条件值的位置
  3. 3.
    得到结果
1
function getBinarySearchLowerBound (array, low, high, target) {
2
// 找到第一个不小于目标值的位置
3
while (low < high) {
4
const mid = Math.floor((low + high) / 2);
5
if (array[mid] < target) {
6
low = mid + 1;
7
} else {
8
high = mid;
9
}
10
}
11
12
// 如果相等,则匹配,否则不匹配
13
return array[low] === target ? low : -1;
14
}
15
16
function getBinarySearchUpperBound (array, low, high, target) {
17
// 找到第一个不大于目标值的位置
18
while (low < high) {
19
const mid = Math.ceil((low + high) / 2);
20
if (array[mid] > target) {
21
high = mid - 1;
22
} else {
23
low = mid;
24
}
25
}
26
27
// 如果相等,则匹配,否则不匹配
28
return array[high] === target ? high : -1;
29
}
30
31
const searchRange = function (nums, target) {
32
const size = nums.length;
33
const low = getBinarySearchLowerBound(nums, 0, size - 1, target);
34
if (low === -1) {
35
return [-1, -1];
36
}
37
// 从左边数字的位置开始
38
const high = getBinarySearchUpperBound(nums, low >= 0 ? low : 0, size - 1, target);
39
return [low, high];
40
};
Copied!
复杂度分析
  • 时间复杂度:
    O(log(n))O(log(n))
    过程中最差情况会遍历二遍数组
  • 空间复杂度:
    O(1)O(1)
    产生三个临时变量存储

数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例1:
1
输入: [3,2,1,5,6,4] 和 k = 2
2
输出: 5
Copied!
示例2:
1
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
2
输出: 4
Copied!
说明:你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

方法一

思路
首先通过快速排序的方法将数组升序排序,此时数组的头部为最小的元素,尾部为数组最大的元素。题目要求找到数组中的第 K 个最大的元素,即返回 length - k 个元素即可。
详解
  1. 1.
    本方法采用快速排序法;
  2. 2.
    首先通过 arr[Math.floor((start + end) / 2)] 找到数组中间的元素作为主元;
  3. 3.
    然后使用双指针,分别从数组的头部和尾部遍历数组;
  4. 4.
    遍历过程中,把比主元小的数都放到主元的左边,比主元大的数都放到主元的右边,实现数组的升序排序;
  5. 5.
    返回第 length - k 个元素,即为数组中第 k 个最大的元素。
1
const findKthLargest = function (nums, k) {
2
return findK(nums, 0, nums.length - 1, nums.length - k);
3
};
4
5
function findK (arr, start, end, k) {
6
if (start === end) return arr[start];
7
// 主元
8
const pivot = arr[Math.floor((start + end) / 2)];
9
let i = start; let j = end;
10
while (i <= j) {
11
while (arr[i] < pivot) i++;
12
while (arr[j] > pivot) j--;
13
if (i <= j) {
14
swap(arr, i, j);
15
i++;
16
j--;
17
}
18
}
19
// 二分查到k位置
20
if (k >= (i - start)) {
21
return findK(arr, i, end, k - i + start);
22
} else {
23
return findK(arr, start, i - 1, k);
24
}
25
}
26
// 元素交换
27
function swap (arr, i, j) {
28
const temp = arr[i];
29
arr[i] = arr[j];
30
arr[j] = temp;
31
}
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogn)O(n log n)
上述解法中,采用了快速排序的方法,快排的时间复杂度
O(nlogn)O(n log n)
  • 空间复杂度:
    O(1)O(1)
上述解法中,申请了四个额外的临时存储空间,这将耗费
O(1)O(1)
的空间。

方法二

思路
首先通过最小堆排序的方法将数组升序排序,排序完的数组如下图所示:
此时数组的头部为最小的元素,尾部为数组最大的元素。题目要求找到数组中的第 K 个最大的元素,即返回 length - k 个元素即可。
详解
  1. 1.
    本方法采用最小堆排序法;
  2. 2.
    首先建立最小堆,将每个叶子结点视为一个堆,再将每个叶子结点与其父节点一起构成一个包含更多结点的堆;
  3. 3.
    所以在构造堆的时候,首先需要找到最后一个结点的父节点,从这个节点开始构造最小堆,直到该节点前面的所有分支节点都处理完毕;
  4. 4.
    然后返回第 length - k 个,即为数组中第 k 个最大的元素。
1
const findKthLargest = function (nums, k) {
2
const size = nums.length;
3
// 建立堆
4
for (let i = parseInt(size / 2) + 1; i >= 0; i--) {
5
heapify(nums, i, size);
6
}
7
// 排序
8
for (let j = size - 1; j >= size - k; j--) {
9
// 得到本次的最大,将最大的与最后一个交换位子
10
swap(nums, 0, j);
11
heapify(nums, 0, j);
12
}
13
return nums[size - k];
14
};
15
16
function heapify (arr, x, length) {
17
// 左右两个子节点
18
const l = 2 * x + 1;
19
const r = 2 * x + 2;
20
let largest = x;
21
if (l < length && arr[l] > arr[largest]) {
22
largest = l;
23
}
24
if (r < length && arr[r] > arr[largest]) {
25
largest = r;
26
}
27
if (largest !== x) {
28
swap(arr, x, largest);
29
// 递归交换以下的是否也建好堆.
30
heapify(arr, largest, length);
31
}
32
}
33
34
function swap (arr, i, j) {
35
const temp = arr[i];
36
arr[i] = arr[j];
37
arr[j] = temp;
38
}
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogn)O(n log n)
上述解法中,采用了堆排序的方法,堆排序的时间复杂度
O(nlogn)O(n log n)
  • 空间复杂度:
    O(1)O(1)
上述解法中,申请了四个额外的临时存储空间,这将耗费
O(1)O(1)
的空间。

方法三

思路
首先通过冒泡排序的方法将数组升序排序,此时数组的头部为最小的元素,尾部为数组最大的元素。题目要求找到数组中的第 K 个最大的元素,即返回 length - k 个元素即可。
详解
  1. 1.
    本方法采用经典冒泡排序法;
  2. 2.
    比较相邻的元素,如果第一个比第二个大,就交换他们两个;
  3. 3.
    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对;
  4. 4.
    完成步骤 3 后,最后的元素会是最大的数,实现升序排序;
  5. 5.
    返回第 len-k 个元素,即为数组中第 k 个最大的元素。
1
const findKthLargest = function (nums, k) {
2
const len = nums.length;
3
for (let i = len - 1; i > 0; i--) {
4
// 冒泡排序
5
for (let j = 1; j <= i; j++) {
6
// 异或交换,详见题外话解析
7
if (nums[j - 1] > nums[j]) {
8
nums[j - 1] ^= nums[j];
9
nums[j] ^= nums[j - 1];
10
nums[j - 1] ^= nums[j];
11
}
12
}
13
if (i === (len - k)) {
14
return nums[i];
15
}
16
}
17
return nums[0];
18
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n2)O(n^2)
上述解法中,内外两层循环,时间复杂度
O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
上述解法中,最优的情况是开始时元素已经按顺序排好,空间复杂度为 0 ,最差的情况是开始时元素逆序排序,此时空间复杂度
O(n)O(n)
,平均空间复杂度
O(1)O(1)
复杂度分析:
  • 时间复杂度:
    O(n2)O(n^2)
    ,内外两层循环,时间复杂度
    O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
    ,最优的情况是开始时元素已经按顺序排好,空间复杂度为0,最差的情况是开始时元素逆序排序,此时空间复杂度
    O(n)O(n)
    ,平均空间复杂度
    O(1)O(1)

题外话

对于给定两个整数a,b,下面的异或运算可以实现a,b的交换,而无需借助第3个临时变量:
1
a = a ^ b;
2
b = a ^ b;
3
a = a ^ b;
Copied!
这个交换两个变量而无需借助第3个临时变量过程,其实现主要是基于异或运算的如下性质:
  1. 1.
    任意一个变量X与其自身进行异或运算,结果为0,即X ^ X=0
  2. 2.
    任意一个变量X与0进行异或运算,结果不变,即X ^ 0=X
  3. 3.
    异或运算具有可结合性,即a ^ b ^ c =(a ^ b)^ c= a ^( b ^ c)
  4. 4.
    异或运算具有可交换性,即a ^ b = b ^ a
分析:
第一步: a = a ^ b;
完成后 a变量的结果为a ^ b
第二步: b = a ^ b;
此时赋值号右边的 a 保存的是 a ^ b 的值,那么将赋值号右边的 a 用 a ^ b 替换,
得到(a ^ b) ^ b = a ^ (b ^ b)=a ^ 0=a,
即经过第二步运算后 b 中的值为 a ,即 b=a ,将 a 换到了 b 里
第三步: a = a ^ b;
此时赋值号右边的 a 保存的仍然是 a ^ b 的值,不变,而赋值号右边的 b 已经是 a 了,
将赋值号右边的 a,b 分别进行替换,
即此时赋值号右边 a ^ b=(a ^ b)^ a=a ^ b^ a=a ^ a^ b=0^ b=b, 该值赋值给 a ,即 a=b
即经过第三步运算后 a 中的值为 b ,即 a=b, 将 b 换到了 a 里
这样经过如上的三步骤,完成了交换两个变量 a,b 而无需借助第 3 个临时变量过程。

颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例
1
输入: [2,0,2,1,1,0]
2
输出: [0,0,1,1,2,2]
Copied!

方法一 直接计算

思路
直接遍历整个数组,分别计算出红蓝白球的个数,然后按照红色、白色、蓝色顺序依次存入数组。
详解
  1. 1.
    设定三个变量 red, white,blue 分别表示红球、白球和蓝球。
  2. 2.
    遍历数组,遇到 0 则使 red 自增1,遇到 1 则使 white 自增1,遇到 2 则使 blue 自增1。
  3. 3.
    根据红白蓝的个数,依次将 0,1,2 存入数组。
1
/**
2
* @param {number[]} nums
3
* @return {void} Do not return anything, modify nums in-place instead.
4
*/
5
const sortColors = function (nums) {
6
let red = 0;
7
let blue = 0;
8
let white = 0;
9
for (let i = 0; i < nums.length; i++) {
10
if (nums[i] === 0) {
11
red++;
12
} else if (nums[i] === 1) {
13
blue++;
14
} else if (nums[i] === 2) {
15
white++;
16
}
17
}
18
let index = 0;
19
for (let i = 0; i < red; i++) {
20
nums[index++] = 0;
21
}
22
for (let i = 0; i < blue; i++) {
23
nums[index++] = 1;
24
}
25
for (let i = 0; i < white; i++) {
26
nums[index++] = 2;
27
}
28
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
  • 空间复杂度:
    O(n)O(n)

方法二 双指针遍历

思路
设定三个指针 begin, end, i,用 i 遍历数组,遇到 0,1 时分别将值与 begin, end 指向的值交换。这种方法相对于方法一的好处是只使用了一个常数空间。
详解
  1. 1.
    设定一头一尾两个指针 begin 和 end,然后用一个指针 i 从头开始遍历数组。
  2. 2.
    如果遇到 0,则将该数值与begin指向的值交换,并且使begin向后移一位。
  3. 3.
    如果遇到 2,则将该数值与end指向的值交换,并且使end向前移一位,并且此时不需自加 i
  4. 4.
    如果遇到 1,则继续。
  5. 5.
    最终得到新数组。
1
/**
2
* @param {number[]} nums
3
* @return {void} Do not return anything, modify nums in-place instead.
4
*/
5
const sortColors = function (nums) {
6
let begin = 0;
7
let end = nums.length - 1;
8
let i = 0;
9
while (i <= end) {
10
if (nums[i] === 0) {
11
nums[i] = nums[begin];
12
nums[begin] = 0;
13
i++;
14
begin++;
15
} else if (nums[i] === 2) {
16
nums[i] = nums[end];
17
nums[end] = 2;
18
end--;
19
} else {
20
i++;
21
}
22
}
23
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)

方法三 使用各种排序法

思路
本题的实质是将数字从小到大排序,可以使用各种排序法(冒泡排序法,选择排序法,快速排序法等),这里举一个冒泡排序法的例子。
1
/**
2
* @param {number[]} nums
3
* @return {void} Do not return anything, modify nums in-place instead.
4
*/
5
const sortColors = function (nums) {
6
for (let i = 0; i < nums.length; i++) {
7
for (let j = 0; j < nums.length - i; j++) {
8
if (nums[j] > nums[j + 1]) {
9
const tem = nums[j];
10
nums[j] = nums[j + 1];
11
nums[j + 1] = tem;
12
}
13
}
14
}
15
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n2)O(n^2)
    遍历了两次含n个元素的空间
  • 空间复杂度:
    O(1)O(1)
    排序过程没有用到新的空间存储数据