二分查找/排序
- 一、前言
- 二、学习刷题网站
- 三、刷题
-
- <1>二分查找-I
- <2>数组中的逆序对
-
- 归并排序
- <3>比较版本号
- 三、小结
一、前言
二分查找和排序是数据结构中重要的一个章节，他的重要性也不言而喻，在未来不管是笔试还是面试都会遇到这类的题目，所以接下来我就会把一些常考的题目全部整理出来供大家学习指正。
二、学习刷题网站
点击下面链接即可进行刷题学习
开始刷题
三、刷题
先说明一下一些题目取自牛客网面试必刷TOP101
里面的一些题目在我以前的文章详细写到过，如果没有用新的方法就不会再做讲解
【剑指Offer】二分法例题
<1>二分查找-I
题目链接
描述
请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
数据范围：0 ≤ len(nums) ≤ 2×10^5， 数组中任意值满足 ∣val∣≤10^9
进阶：时间复杂度O(logn) ，空间复杂度 O(1)
示例1
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在nums中并且下标为 6
示例2
输入：[],3
返回值：-1
说明：nums为空，返回-1
示例3
输入：[-1,0,3,4,6,10,13,14],2
返回值：-1
说明：2 不存在nums中因此返回 -1
思路分析：
这道题很显然要用二分查找，每次都取中间的数据跟目标数据比较，以此来缩小区间，要注意left和right相等时也要比较。
int search(int* nums, int numsLen, int target ) {
int left = 0, right = numsLen - 1;
while(left <= right)
{
int mid = (left + right) >> 1;
if(nums[mid] < target)
{
left = mid + 1;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
<2>数组中的逆序对
题目链接
描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围： 对于50% 的数据,size ≤ 10^4
对于100% 的数据, size ≤ 10^5
数组中所有数字的值满足 0 ≤ val ≤ 1000000
要求：空间复杂度O(n)，时间复杂度O(nlogn)
输入描述：
题目保证输入的数组中没有的相同的数字
示例1
输入：[1,2,3,4,5,6,7,0]
返回值：7
示例2
输入：[1,2,3]
返回值：0
思路分析：
首先因为复杂度的要求暴力求解行不通。那么我们就可以用归并法：
归并排序
归并排序的方法就不过多介绍，在我以前的文章里有详细介绍：八大排序，你都掌握了吗？
首先看一个问题：假设有两个区间[4, 5] 和 [2, 3]他的逆序对数为(4, 2), (4, 3), (5, 2), (5, 3)，如果不是有序的呢？
[5，4] 和 [3，2]（同一区间已经计算过）结果还是4个，那么拍成有序有必要吗？
答案是有必要
可以看这样一个场景：
两个区间[4, 5]和[2, 3]我们知道4 > 2，那么显然4 后面的数字都大于2，就可以方便我们计数。
void merge(int* data, int* tmp, int left, int right, long* k)
{
if(left >= right)
{
return;
}
int mid = (left + right) >> 1;
merge(data, tmp, left, mid, k);
merge(data, tmp, mid + 1, right, k);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//放入tmp数组
int i = left;
while(begin1 <= end1 && begin2 <= end2)
{
if(data[begin1] < data[begin2])
{
tmp[i++] = data[begin1];
begin1++;
}
else
{
tmp[i++] = data[begin2];
(*k) += (end1 - begin1 + 1);
begin2++;
}
}
while(begin1 <= end1)
{
tmp[i++] = data[begin1++];
//(*k) += len;
}
while(begin2 <= end2)
{
tmp[i++] = data[begin2++];
}
//把tmp拷贝回去
for(int j = left; j <= right; j++)
{
data[j] = tmp[j];
}
}
int InversePairs(int* data, int dataLen ) {
int* tmp = (int*)malloc(sizeof(int) * dataLen);
int left = 0, right = dataLen - 1;
long k = 0;
merge(data, tmp, left, right, &k);
return k % 1000000007;
}
<3>比较版本号
题目链接
描述
牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
现在给你2个版本号version1和version2，请你比较他们的大小
版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号
每个版本号至少包含1个修订号。
修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
比较规则：
一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.
数据范围：
1 <= version1.length, version2.length <= 10001<=version1.length,version2.length<=1000
version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围
进阶： 时间复杂度 O(n)
示例1
输入：“1.1”,“2.1”
返回值：-1
说明：version1 中下标为 0 的修订号是 “1”，version2 中下标为 0 的修订号是 “2” 。1 < 2，所以 version1 < version2，返回-1
示例2
输入：“1.1”,“1.01”
返回值：0
说明：version2忽略前导0，为"1.1"，和version相同，返回0
示例3
输入：“1.1”,“1.1.1”
返回值：-1
说明：“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1
示例4
输入：“2.0.1”,“2”
返回值：1
说明：version1的下标2>version2的下标2，返回1
示例5
输入：“0.226”,“0.36”
返回值：1
说明：226>36，version1的下标2>version2的下标2，返回1
思路分析：
这道题最令人头疼的是前置0，那么我们就可以把每个.之前的字符串转换为数字，然后比较，就可以消除前置0的影响。
int compare(char* version1, char* version2 ) {
int sz1 = strlen(version1), sz2 = strlen(version2);
int i = 0, j = 0;
while(i < sz1 || j < sz2)
{
//统计.之前的数字
long long num1 = 0, num2 = 0;
while(i < sz1 && version1[i] != '.')
{
num1 = num1 * 10 + (version1[i] - '0');
i++;
}
//跳过.
i++;
while(j < sz2 && version2[j] != '.')
{
num2 = num2 * 10 + (version2[j] - '0');
j++;
}
//跳过.
j++;
//比较大小
if(num1 < num2)
{
return -1;
}
else if(num1 > num2)
{
return 1;
}
}
return 0;
}
三、小结
二分查找是在面试中考的非常多的知识点，一定要掌握方法，排序的八种方法也要烂熟于心。
点击链接一起刷题吧
相关文章
