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;
}
};
nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!