LeetCode704.二分查找、27.移除元素、977.有序数组的平方
Leetcode 704. 二分查找
给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果target存在返回下标，否则返回-1。
你必须编写一个具有O(log n)时间复杂度的算法。
题目链接：
https://leetcode.cn/problems/binary-search/
文章讲解：
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：
https://www.bilibili.com/video/BV1fA4y1o715
我的思路：
在数组的第一个位置和最后一个位置分别设置一个low指针和一个high指针，在数组的中间位置（即mid=(low+high)/2）设置一个mid指针。
若mid指针所指元素小于目标值target，则将low指针移动到mid指针所指的右侧第一个位置。
若mid指针所指元素大于目标值target，则将high指针移动到mid指针所指的左侧第一个位置。
若mid指针所指元素等于目标值target，则返回mid所指位置的下标。
若mid不等于target，则重复上述判断。
若数组的每一个元素都不等于target，则返回-1。
我的代码：
int search(int* nums, int numsSize, int target) { int low=0,high=numsSize-1; while(low<=high){ int mid=(low+high)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target) low=mid+1; else if(nums[mid]>target) high=mid-1; } return -1; }二分查找法，也称折半查找法，只适用于有序数组，且数组中无重复元素。
（若有重复元素，则返回的元素下标可能不是唯一的。）
写二分法要注意区间边界，区间的定义一般分为两种：左闭右闭即[low, high]和左闭右开即[low, high)。
第一种写法：左闭右闭
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
代码如下：（就是我前面的想法）
int search(int* nums, int numsSize, int target) { int low=0,high=numsSize-1; while(low<=high){ int mid=(low+high)/2; if(nums[mid]<target) low=mid+1; else if(nums[mid]>target) high=mid-1; else return mid; } return -1; }第二种写法：左闭右开
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
代码如下：（不习惯用这个）
int search(int* nums, int numsSize, int target) { int low=0,high=numsSize; while(low<high){ int mid=(low+high)/2; if(nums[mid]<target) low=mid+1; else if(nums[mid]>target) high=mid; else return mid; } return -1; } 相关题目推荐35.搜索插入位置(opens new window)34.在排序数组中查找元素的第一个和最后一个位置(opens new window)69.x 的平方根(opens new window)367.有效的完全平方数
LeetCode 27. 移除元素
给你一个数组nums和一个值val，你需要 原地 移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。
假设nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：更改nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。
题目链接：
https://leetcode.cn/problems/remove-element/
文章讲解：
https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：
https://www.bilibili.com/video/BV12A4y1Z7LP
我的思路：
设置两个指针 i 和 j ，初始均指向数组的第一个元素，i 用于记录最新非删除元素的位置，j 用于向后查找需删除的元素，再设置一个int型变量 k 记录循环的轮数。
当 k 小于数组长度时，进入循环：
若 j 所指的元素不等于val，则将 j 所指元素赋值到 i 所指元素上，i 和 j 一起向后移动一个元素。
若 j 所指的元素等于val，则只将 j 向后移动一个元素，继续寻找需删除的元素。
以上判断结束后，轮数 k 加1，知道不满足条件为止，退出循环，返回 i。
我的代码：
int removeElement(int* nums, int numsSize, int val) { int i=0,j=0,k=0; while(k<numsSize){ if(nums[j]!=val && i<=j){ nums[i]=nums[j]; i++; j++; } else if(nums[j]==val) j++; k++; } return i; }暴力解
两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。时间复杂度是O(n^2)。
代码如下：
int removeElement(int* nums, int numsSize, int val) { for(int i=0;i<numsSize;i++){ if(nums[i]==val){// 发现需要移除的元素，就将数组集体向前移动一位 for(int j=i+1;j<numsSize;j++) nums[j-1]=nums[j]; i--;// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位 numsSize--;// 此时数组的大小-1 } } return numsSize; }快慢指针
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
代码如下：（和我写的差不多）
int removeElement(int* nums, int numsSize, int val) { int slow=0; for(int fast=0;fast<numsSize;fast++) if(nums[fast]!=val) nums[slow++]=nums[fast]; return slow; }相关题目推荐26.删除排序数组中的重复项(opens new window)283.移动零(opens new window)844.比较含退格的字符串(opens new window)977.有序数组的平方
LeetCode 977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。题目链接：
https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：
https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解：
https://www.bilibili.com/video/BV1QB4y1D7ep
双指针法
数组其实是有序的， 只不过负数平方后可能成为最大数，那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
i 指向数组起始位置，j 指向数组终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] ，那么result[k--] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] ，那么result[k--] = A[i] * A[i]; 。
int* sortedSquares(int* nums, int numsSize, int* returnSize) { //数据类型* 数组名 = (数据类型*)malloc(数组长度 * sizeof(数据类型)); int* result=(int*)malloc(numsSize*sizeof(int)); int k=numsSize-1; for(int i=0,j=numsSize-1;i<=j;){ if(nums[i]*nums[i]>nums[j]*nums[j]){ result[k--]=nums[i]*nums[i]; i++; } else{ result[k--]=nums[j]*nums[j]; j--; } } *returnSize = numsSize;//设置返回数组的大小 return result; }注意：return只能直接返回一个值 / 一个指针，无法直接返回多个独立值。
如果删掉*returnSize = numsSize;，会导致：
- 调用者无法获取返回数组的长度：调用者拿到
result指针后，不知道该遍历多少次（比如调用者写for(int i=0; i<returnSize; i++)，returnSize是随机值，会导致数组越界、程序崩溃）； - 违反题目隐含要求：OJ（在线判题系统）会通过
returnSize校验返回数组的长度是否正确，直接判错。
暴力解
每个数平方之后，进行快速排序。
