一、数组
1、二分查找
704. 二分查找
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间
题目分析
本题是二分法的模板题目
补充: 要是寻不到则返回 次小的数事,该如何返回呢 ? return right; 可以参考图解进行分析
其实最后结果无非是两种
(1)left=middle+1从而导致,left > right.
(2)right=middle-1,从而导致,left>right.两种情况下都是返回right的.
图解:
参考代码
#include<bits/stdc++.h> using namespace std; //方法一:左闭右闭[left,right] int search(vector<int>& nums, int target) { int left,right,middle; left = 0; right = nums.size()-1; while(left<=right) { //return right middle = left+(right-left)/2; if(target>nums[middle]) { left = middle+1; } else if(target<nums[middle]) {// 6 6 right = middle - 1; } else { return middle; } } return -1; } //方法二:左闭右开[left,right) int search(vector<int>& nums, int target) { int left,right,middle; left = 0; right = nums.size(); while(left<right){ middle = left+(right-left)/2; if(target>nums[middle]){//left 4 middle 5 left = middle+1; }else if(target<nums[middle]) { right = middle; }else{ return middle; } } return -1; }
35.搜索插入位置
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0 输出: 0
示例 5:
输入: nums = [1], target = 0 输出: 0
思路分析
方法一:暴力法
要在数组中插入目标值，无非是这四种情况。
- 目标值在数组所有元素之前
- 目标值等于数组中某一个元素
- 目标值插入数组中的位置
- 目标值在数组所有元素之后
方法二:二分法
参考代码
暴力法
//方法一:暴力法 int searchInsert(vector<int>& nums, int target) { for(int i = 0; i <nums.size(); i++) { // 分别处理如下三种情况 // 目标值在数组所有元素之前 // 目标值等于数组中某一个元素 // 目标值插入数组中的位置 if(target>=nums) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果 return i+1; } } // 目标值在数组所有元素之后的情况 return nums.size();// 如果target是最大的，或者 nums为空，则返回nums的长度 }
二分法
int searchInsert(vector<int>& nums, int target) { int left = 0,right = nums.size() - 1,mid; while(left <= right) { mid = (left+right) / 2; if(target > nums[mid]) { left = mid + 1; } else if(target < nums[mid]) { right = mid - 1; } else { return mid; } } return right+1;//right为<target的最大元素的下标.所以要插入的位置为right+1 }
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
思路分析
方法一:二分法(自己的做法)
先找到一个符合的,再从中间到两边寻找边界.
方法二: 二分法(Carl大佬的做法)
寻找target在数组里的左右边界，有如下三种情况：
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
参考代码
二分法1
//二分搜索 vector<int> searchRange(vector<int>& nums, int target) { int begin = -1,end = -1,left = 0,right = nums.size()-1,mid; while(left <= right) { mid = (left+right)/ 2; if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] < target) { left = mid + 1; } else { break; } } if(left <= right) { //找到了概述 for(int i = mid; i >=0; i--) { //向左寻找左边界 if(nums[i]==target) { begin = i; } else { break; } } for(int i = mid; i<nums.size(); i++) { if(nums[i]==target) { end = i; } else { break; } } } return {begin,end}; }
二分法(Carl的做法),目前还在理解中…
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int leftBorder = getLeftBorder(nums, target); int rightBorder = getRightBorder(nums, target); // 情况一 if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; // 情况三 if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1}; // 情况二 return {-1, -1}; } private: int getRightBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况 while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else { // 寻找右边界，nums[middle] == target的时候更新left left = middle + 1; rightBorder = left; } } return rightBorder; } int getLeftBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况 while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right right = middle - 1; leftBorder = right; } else { left = middle + 1; } } return leftBorder; } };
69. Sqrt(x)
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
思路分析
二分法的使用
参考代码
int mySqrt(int x) { //特殊值判断 if(x==0) { return 0; } if(x==1) { return 1; } long long left = 1,right = x / 2,mid; while(left<=right) { mid = left + (right-left) / 2; if(mid * mid > x) { right = mid - 1; } else if(mid * mid < x) { left = mid + 1; } else { return (int)mid;//如果正好找到了 } } return (int)right;//如果没有找到,则返回小于 Sqrt(x)的最大整数,也就是right. }
367. 有效的完全平方数
题目描述
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true
示例 2：
输入：num = 14 输出：false
思路分析
二分法的使用
参考代码
#include<bits/stdc++.h> uisng namespace std; bool isPerfectSquare(int num) { if(num==0 || num = 1) { return true; } long long left = 1,right = num / 2;//除了0和1 其他的数num的开方都 <= num/2 while(left<=right) { mid = left + (right-left) / 2; if(mid * mid > num) { right = mid - 1; } else if(mid * mid < num) { left = mid + 1; } else { return true; } } return false; }
2、双指针法
27. 移除元素
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
题目分析
方法一 暴力解法
思路:两层for循环,外层循环来遍历每一个元素,判断是否和val相等.内层循环,在找到和val相等的元素后进行整体前移.
方法二双指针法
快的指针来遍历每一个元素,慢的指针来控制下一次有效元素存放的位置.
参考代码
暴力法
//方法一:暴力枚举法--双层循环 int removeElement(vector<int>& nums, int val) { int size = nums.size(); for(int i = 0; i <size; i++) { //判断是否是目标元素 if(nums[i]==val) { //将i元素后面的都往前移动一位,覆盖当前元素. for(int j = i+1; j < size; j++) { //将元素往前移动 nums[j-1] = nums[j]; } size--; i--;//因为覆盖过了,下一次依旧从当前位置开始判断 } } return size; } //注意两个循环的条件位置必须写size,否则会陷入死循环,一直判断.
双指针法
//方法二:双指针(快慢指针) int removeElement(vector<int>& nums, int val) { int slowIndex,fastIndex; slowIndex = 0; for(fastIndex = 0;fastIndex<nums.size();fastIndex++) {//fastIndex遍历整个数组 if(nums[fastIndex]!=val){//slowIndex控制将和目标不相同的元素从前往后依次放置. nums[slowIndex++] = nums[fastIndex] ; } } return slowIndex; }
