二分查找/排序 一、前言二、学习刷题网站三、刷题<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; }三、小结
二分查找是在面试中考的非常多的知识点，一定要掌握方法，排序的八种方法也要烂熟于心。
点击链接一起刷题吧
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |