包头市建设工程质量监督站网站,南京市高淳县建设厅网站,高端的深圳网站页面设计,著名设计师网站文章目录一、在排序数组中查找数字二、0~n-1中缺失的数字三、旋转数组的最小数字四、二维数组中的查找一、在排序数组中查找数字
题目传送门 法一#xff1a;暴力解 直接遍历然后计数
法二#xff1a;二分法求边界 看到关键字排序数组、有序数组#xff0c;一定要想到二分…
文章目录一、在排序数组中查找数字二、0~n-1中缺失的数字三、旋转数组的最小数字四、二维数组中的查找一、在排序数组中查找数字
题目传送门 法一暴力解 直接遍历然后计数
法二二分法求边界 看到关键字排序数组、有序数组一定要想到二分的方法效率高思路也比较简单 思路使用二分法、找数组的左边界(left)和右边界(right)最后目标数字个数就是right-left1 对于二分法我们可以分别求左边界和右边界也可以二分求左边界之后接着遍历计数两种情况对应在真实场景下连续相等的数据一般有多长。如果经常出现很长一串连续相等的数据就用二分法求右边界否则容易使算法退化到O(N)。PS: 在C 11 标准中nums.size()的时间复杂度是Constant常数级O(1) class Solution {
public:int search(vectorint nums, int target) {int res0;int idxgetFirstIndex(nums,target);if(idx-1) return res;for(int iidx;inums.size()nums[i]target;i){res;}return res;}int getFirstIndex(vectorint nums,int target){int left0;int rightnums.size()-1;int res-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){rightmid-1;}else if(nums[mid]target){leftmid1;}else{resmid;rightmid-1;} }return res;}
};标准解法
class Solution {
public:int binarySearch(vectorint nums, int target, bool lower) {int left 0, right (int)nums.size() - 1, ans (int)nums.size();while (left right) {int mid (left right) / 2;if (nums[mid] target || (lower nums[mid] target)) {right mid - 1;ans mid;} else {left mid 1;}}return ans;}int search(vectorint nums, int target) {int leftIdx binarySearch(nums, target, true);int rightIdx binarySearch(nums, target, false) - 1;if (leftIdx rightIdx rightIdx nums.size() nums[leftIdx] target nums[rightIdx] target) {return rightIdx - leftIdx 1;}return 0;}
};二、0~n-1中缺失的数字
题目传送门 思路因为有序所以可以看看下标是否等于数组中的对应元素 初始化 左边界 left 0 右边界 right len(nums)−1 代表闭区间 [left, right] 。 循环二分 当 left ≤ right 时循环 即当闭区间 [left, right] 为空时跳出 1、计算中点 mid (left right)//2 其中 “//” 为向下取整除法 2、若 nums[mid] mid 说明mid前面的元素肯定都是完整的不少元素所以只需要继续二分右边的数组即可则 “右子数组的首位元素” 一定在闭区间 [mid1, right] 中因此执行 left mid1 3、若 nums[mid] ! mid 说明mid前面的元素就有少的所以只要继续二分左边的数组即可则 “左子数组的末位元素” 一定在闭区间 [left, mid−1] 中因此执行 right mid−1 4返回值 跳出时变量 i 和 j 分别指向 “右子数组的首元素” 和 “左子数组的末元素” 。因此返回 i 即可。 class Solution {
public:int missingNumber(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int mid(leftright)/2;if(nums[mid]mid){leftmid1;}else{rightmid-1;}}return left;}
};三、旋转数组的最小数字
题目传送门 题目分析 旋转数组把一个有重复数字的有序数组末位一部分移动到头部这就叫做旋转数组。在这里插入图片描述
我们的目标就是找到这个分界点 法一暴力 分界点右边的第一个数字就是我们要找的最小数字 其实可以类比数学中的找极点
class Solution {
public:int minArray(vectorint numbers) {// 注意i0开始要越界特殊处理一下从1开始可以避免for(int i1;inumbers.size();i){if(numbers[i-1]numbers[i])return numbers[i];}return numbers[0];}
};法二二分法 题目说了可能存在重复的数字 ---------------------
class Solution {
public:int minArray(vectorint numbers) {int left0;int rightnumbers.size()-1;if(right0) return numbers[0];while(leftright){int midleft(right-left)/2;if(numbers[mid]numbers[right])leftmid1;else if(numbers[mid]numbers[right])rightmid;elseright--;}return numbers[left];}
};四、二维数组中的查找
TP 法一暴力 直接遍历矩阵判断有没有target
class Solution {
public:bool findNumberIn2DArray(vectorvectorint matrix, int target) {for(auto row: matrix){for(auto e: row){if(etarget)return true;}}return false;}
};时间复杂度O(MN) 空间复杂度O(1)
法二行二分 对二维数组每一行进行二分查找
class Solution {
public:bool findNumberIn2DArray(vectorvectorint matrix, int t) {if (matrix.size() 0 || matrix[0].size() 0) return false;int n matrix.size(), m matrix[0].size();int l 0, r 0, mid 0;for (int i 0; i n; i ) {l 0;r m - 1;while (l r) {mid l (r - l) / 2;if (matrix[i][mid] t) return true;if (matrix[i][mid] t) l mid 1;if (matrix[i][mid] t) r mid - 1;} }return false;}
};时间复杂度O(MlogN) 空间复杂度O(1)
法三Z字形查找
class Solution
{
public:bool findNumberIn2DArray(vectorvectorint matrix, int target){int i matrix.size() - 1; // 行int j 0; // 列if (matrix.size() 0 || matrix[0].size() 0)return false;while (i 0 j matrix[0].size() - 1){if (matrix[i][j] target)i--;else if (matrix[i][j] target)j;elsereturn true;}return false;}
};时间复杂度O(MN) MN为矩阵的行数和列数 空间复杂度O(1)
