代码随想录算法训练营第一天 | 704. 二分查找、 27. 移除元素、977.有序数组的平方 （上）

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

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

 

二分查找问题的关键在于边界条件的选择决定了判断条件的设置。以下从左闭右闭区间和左闭右开区间两种写法来说明。这里其实有一点，就是题目给出的是左闭右闭也好，左闭右开也好，都可以使用两种解法，不会影响。

左闭右闭：即left的值和right的值都可以取到，二分查找是在单调数列中，通过不断判断中间值的方法来逐渐缩小所查的范围。某种意义上和猜数字的游戏类似，只不过我们固定了每次都猜中间数字。这样可以最高效率猜到这个数字的位置。

在左闭右闭的情况下，我们定义left为0，right为数组大小-1，这样可以让right的编号正好对应数组的最后一个值，也就是取满数组。

第二步，考虑最外的大循环，当left和right非常接近的时候就可以停止循环了。在闭区间中，left是可以等于right的，于是我们设置判断条件为left<=right，只有当left大于right时退出循环。

第三部，在大循环内部我们需要根据target的位置来选择更新left或right。这里我们需要定义middle的值为(left+right)/2。这一步我看很多人说可以定义为left+（right-left）/2，可以防止溢出，我其实不太理解，个人认为可能是如果当right太大的时候两个数相加会超过int的范围。

定义好middle后，我们比较原数组在middle位置的数值和target，当大于target的时候，说明目标数在left和middle中间，于是我们需要更新right值，此时由于我们选择了左闭右闭区间，middle位置的数确定不是target了，那么right就可以等于middle-1，因为我们不需要重复判断middle，可以直接把它排除在外。

当小于target也是同理，说明目标数在middle和right中间，于是我们更新left的值，和前面同样道理，并不需要将middle放入我们待判断的区间中，于是left可以为middle+1。

那么其他情况显然middle等于target，此时输出middle即可。大循环后return-1即可。代码如下：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;//左闭右闭区间，right直接对应数组最后一个元素的序号即可while(left <= right){ // 当left==right，区间[left, right]依旧合法，用 <=int middle = left + ((right - left) / 2);//防止溢出，大概是防止int型不够存if(nums[middle] > target){right = middle - 1;// target 在左，将已经判断过的middle排除，所以[left, middle - 1]}else if(nums[middle] < target){left = middle + 1; // target 在右，将已经判断过的middle排除，所以[middle + 1, right]}else{return middle;// 找到目标} }// 未找到目标时return -1;}
};

左闭右开：

道理和前一种类似，代码如下：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size();//左闭右开区间，right需要对应数组最后一个元素的序号+1来保证能遍历题目闭区间数组中所有的数while(left < right){ // 当left=right，区间[left, right）不合法，用 <int middle = left + ((right - left) / 2);//防止溢出，大概是防止int型不够存if(nums[middle] > target){right = middle;// target 在左，将已经判断过的middle排除，所以[left, middle）}else if(nums[middle] < target){left = middle + 1; // target 在右，将已经判断过的middle排除，所以[middle + 1, right）}else{return middle;// 找到目标} }// 未找到目标时return -1;}
};

35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，这俩明天再看。

2-27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100 

   

 

涉及数组概念相关问题，简单的暴力解法为，直接两层循环，第一层寻找元素并删除，第二层将所有元素提前一位即可。下面给出代码：

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0;i < size; i++){if (val == nums[i]){for(int j = i + 1; j < size; j++){nums[j - 1] = nums[j];}i--;size--;}}return size;}
};

今天目前先到这里，27的双指针实现和977题目明天一起做。