leetcode排序和搜索常见面试算法题

什么叫ARTS?

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

作者:陈皓
链接:https://www.zhihu.com/question/301150832/answer/529809529
来源:知乎

_Merge Sorted Array

给两个有序数组排序,排序后合并到数组1中。

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]
方法一
  1. 采用双指针法,同时遍历两个数组。
  2. 比较遍历到的数,将较小的数提取到临时数组,临时指针++,较小数组遍历指针++,如果相等,将这个等数提取到临时数组,需要存两次,同时两个数组的遍历指针++。
  3. 直到有一方遍历完成,将另外未遍历完的直接插入临时数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=0,j=0;
vector<int> temp;
while(i<m && j<n) {
if(nums1[i]==nums2[j]) {
temp.push_back(nums1[i]);
temp.push_back(nums1[i]);
i++;
j++;
} else if(nums1[i]<nums2[j]) {
temp.push_back(nums1[i]);
i++;
} else {
temp.push_back(nums2[j]);
j++;
}
}
for(;i<m;i++)
temp.push_back(nums1[i]);
for(;j<n;j++)
temp.push_back(nums2[j]);
nums1=temp;
}
};
方法二
  1. 排完序的数组1总共有m+n位,从两数组末尾m,n处同时遍历数组,将大的数存入数组1的m+n末尾,大的数存入后还需要移动指针,相等的数需要存入两次,两个数组的指针都需要移动一次。
  2. 遍历完成,再将剩下未遍历完的数组补上到数组1的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=m-1,j=n-1,k=m+n-1;
while(i>=0 && j>=0) {
if(nums1[i]==nums2[j]) {
nums1[k--]=nums1[i--];
nums1[k--]=nums2[j--];
} else if(nums1[i] > nums2[j]) {
nums1[k--]=nums1[i--];
} else {
nums1[k--]=nums2[j--];
}
}
while(i>=0)
nums1[k--]=nums1[i--];
while(j>=0)
nums1[k--]=nums2[j--];
}
};

First Bad Version

找到第一个坏版本

1
2
3
4
5
6
7
Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.
方法一
  1. 采用折半查找,先找一半的那个数是否是坏版本,如果不是则向前找一半,如果是,则向后找一半。折半查找的方法为定义一个low,high,不断缩减范围,注意跳出循环的条件。
  2. 直到无法寻找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int low=1, high=n, mid=1;
while(high>low) {
mid=low+(high-low)/2;
if(isBadVersion(mid)) {
high=mid;
} else {
low=mid+1;
}
}
return high;
}
};

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
int low=0, high=n;
while(high-low>1) {
int mid=low+(high-low)/2;
if(isBadVersion(mid)) {
high=mid;
} else {
low=mid;
}
}
return high;
}
};

数组中的第K个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
int partition(vector<int>& nums, int left, int right) {
int randomIndex = right;
int pivot = nums[right];
int i = left;
int j = right - 1;

while (true) {
while (i <= j && nums[i] < pivot) {
i++;
}

while (i <= j && nums[j] > pivot) {
j--;
}

if (i >= j) {
break;
}
swap(nums, i, j);
i++;
j--;
}

swap(nums, right, i);
return i;
}

void swap(vector<int>& nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}

int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
int target = len - k;

int left = 0;
int right = len - 1;

while (true) {
int pivotIndex = partition(nums, left, right); // 分治思想
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
left = pivotIndex + 1;
} else {
right = pivotIndex - 1;
}
}
}
};

排序数组

给你一个整数数组 nums,请你将该数组升序排列。

1
2
输入:nums = [5,2,3,1]
输出:[1,2,3,5]

插入排序

内部循环中,首先将 j 的值赋值为 i-1,这是因为我们将 i-1 视为已排序的序列的最后一个元素。然后,我们进行一个 while 循环,只要 j 大于等于 0 并且当前考虑的数 arr[j] 大于 key,我们就将该元素右移一位,继续向左比较。最后,我们将 key 插入到最终的位置 j+1 上,以此来完成插入过程。

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(vector<int>& nums,int n)
{
for(int i=0;i<n;i++) {
int temp = nums[i];
int j = i-1;
while(j >= 0 && nums[j] >temp) {
nums[j+1] = nums[j];
j--;
}
nums[j+1] = temp;
}
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort(vector<int>& nums,int n)
{
for(int i=0;i<n-1;i++) {
bool flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
if(flag == false){
return ;
}
}
}

快排

arr是待排序的整数数组,left 和 right 表示列表的左右边界。在 partition() 函数中,我们选取左边第一个元素作为枢轴(pivot),并使用 i 和 j 两个指针在列表中进行从左到右和从右到左的扫描。在扫描的过程中,如果发现 i 指向的元素大于枢轴,或者 j 指向的元素小于枢轴,则将 i 和 j 指向的元素进行交换。最终,当 i 大于 j 时,将枢轴与 j 指向的元素进行交换,并返回 j。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void QuickSort(vector<int>& nums,int low,int high)
{
if(low<high) {
int pivot = partition(nums, low, high);
QuickSort(nums,low,pivot-1);
QuickSort(nums,pivot+1,high);
}
}
int partition(vector<int>& arr, int left, int right)
{
int pivot = arr[left];
int i = left + 1;
int j = right;

while (i <= j) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}

swap(arr[left], arr[j]); // 和基准相反的那个数
return j;
}

// 优化版,防止退化为选择排序
int partition(vector<int>& arr, int left, int right)
{
int randidx = left + rand() % (right - left + 1);
int pivot = arr[randidx];
swap(arr[left], arr[randidx]);
int i = left + 1;
int j = right;

while (i <= j) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}

swap(arr[left], arr[j]); // 和基准相反的那个数
return j;
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SelectSort(vector<int>& nums,int n)
{
//遍历数组
for(int i=0;i<n-1;i++) {
//找到未排序部分的最小元素
int min = i;
for(int j=i+1;j<n;j++) {
if(nums[j]<nums[min]) min = j;

}
//将找到的最小元素移动到已排序部分的末尾
if(min!=i) swap(nums[i],nums[min]);
}
}

堆排序

最大堆是一种完全二叉树(即除最后一层外,每一层上的节点数都达到最大值,最后一层的节点集中在左侧),其中每个节点的值都大于其子节点的值。因此,根节点是最大值。
最大堆常常用于堆排序等算法中,可以快速寻找并删除最大值。在堆排序中,通过不断将堆顶元素与未排序部分的最后一个元素交换,并重新堆化剩下的完全二叉树(除去最后一个节点),可以得到一个有序数组。
堆排序的核心思想是不断将堆顶的最大元素(或最小元素)放到已排序部分,然后缩小堆范围,重建堆,继续取出下一个最大元素,直到整个数组有序。这个算法的时间复杂度通常为O(n log n),它是一种原地排序算法,适用于大规模数据集。

  1. 构建堆:首先,将未排序的数组看作是一个二叉树,然后从底部开始,将数组转化为一个堆。这个堆可以是最大堆或最小堆,具体取决于你想升序还是降序排序。在最大堆中,父节点的值大于子节点,而在最小堆中,父节点的值小于子节点。
  2. 取出根节点:在堆中,根节点通常是最大(或最小)的元素。将根节点与数组中的最后一个元素交换。
  3. 重建堆:去掉根节点后,重新调整堆,使其保持堆的性质。这通常涉及将新的根节点(之前的最后一个元素)下沉到合适的位置,以确保堆的性质仍然得以维持。
  4. 重复操作:重复以上两个步骤,不断取出根节点并重建堆,直到堆为空。每次取出的根节点都是未排序部分中最大(或最小)的元素。
  5. 得到有序数组:当所有元素都被取出并重新构建堆后,你就得到了一个有序的数组。
    堆的实现通常使用数组,其中每个节点用一个数组元素表示。具体来说,假设当前节点的下标为i,则其左子节点的下标为2i+1,右子节点的下标为2i+2,其父节点的下标为(i-1)/2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
using namespace std;

// 递归方式构建大根堆(len是arr的长度,index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
int left = 2*index + 1; // index的左子节点
int right = 2*index + 2;// index的右子节点

int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;

if(maxIdx != index)
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx);
}
}

// 堆排序
void heapSort(vector<int> &arr, int size)
{
// 构建大根堆(从最后一个非叶子节点向上)
for(int i=size/2 - 1; i >= 0; i--)
{
adjust(arr, size, i);
}

// 调整大根堆
for(int i = size - 1; i > 0; i--)
{
swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
adjust(arr, i, 0); // 将未完成排序的部分继续进行堆排序
}
}

int main()
{
vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
heapSort(arr, arr.size());
for(int i=0;i<arr.size();i++)
{
cout<<arr[i]<<endl;
}
return 0;
}

搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i=0;
int j=matrix[0].size()-1;
while(i<matrix.size() && j>=0)
{
if(matrix[i][j]>target) // 转二分查找
j--;
else if(matrix[i][j]<target)
i++;
else
return true;
}
return false;
}

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

我们可以归纳出三种情况:

  • 如果A[k/2-1]<B[k/2-1],则比A[k/2-1]小的数最多只有A的前k/2-1个数和B的前k/2-1个数,即比A[k/2-1]小的数最多只有k-2个,因此A[k/2-1]不可能是第k个数,A[0]到A[k/2-1]也都不可能是第k个数,可以全部排除。
  • 如果A[k/2-1]>B[k/2-1],则可以排除B[0]到B[k/2-1]。
  • 如果A[k/2-1]=B[k/2-1],则可以归入第一种情况处理。


可以看到,比较 A[k/2−1] 和 B[k/2−1] 之后,可以排除 k/2 个不可能是第 k 小的数,查找范围缩小了一半。同时,我们将在排除后的新数组上继续进行二分查找,并且根据我们排除数的个数,减少 k 的值,这是因为我们排除的数都不大于第k 小的数。

有以下三种情况需要特殊处理:

  1. 如果 A[k/2−1] 或者 B[k/2−1] 越界,那么我们可以选取对应数组中的最后一个元素。在这种情况下,我们必须根据排除数的个数减少k 的值,而不能直接将 k 减去 k/2。
  2. 如果一个数组为空,说明该数组中的所有元素都被排除,我们可以直接返回另一个数组中第k 小的元素。
  3. 如果 k=1,我们只要返回两个数组首元素的最小值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
/* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数
*/

int m = nums1.size();
int n = nums2.size();
int index1 = 0, index2 = 0;

while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}

// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
else {
return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
};
nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!