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]
解题思路：二分法找target
（1）找到后flag标记为0,往mid两边找起始和结束位置
（2）未找到，a[0]=-1,a[1]=-1
首先要malloc分配数组空间，malloc头文件为<stdlib.h>,*returnSize为返回数组的大小。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int left=0,right=numsSize-1,mid,flag=1;//flag=1表示未找到
int *a=malloc(sizeof(int)*2);
while(left<=right&&flag){
mid=left+(right-left)/2;
if(nums[mid]>target)right=mid-1;
else if(nums[mid]<target)left=mid+1;
else flag=0;
}
if(flag) a[0]=-1,a[1]=-1;
else{
int start=mid,end=mid;
for(int i=mid+1;i<numsSize;i++){
if(nums[i]==target)end=i;
}
for(int i=mid-1;i>=0;i--){
if(nums[i]==target)start=i;
}
a[0]=start,a[1]=end;
}
*returnSize=2;
return a;
}时间复杂度分析，二分查找部分时间复杂度为 O(log n) ，确定边界时间复杂度为O(n),所以，整个函数时间复杂度为O(n)，不满足题目时间复杂度要求，换一种解法。
解题思路：利用两个函数二分法寻找左右边界,初始值为-1
寻找左边界findL函数，如果nums[mid]==target,左边界设置为mid，向左寻找左边界，故right=mid-1,其他与二分法思路一致。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int findL(int *nums,int numsSize,int target){
int left=0,right=numsSize-1,mid,L=-1;
while(left<=right){
mid=left+(right-left)/2;//防止溢出
if(nums[mid]>target)right=mid-1;
else if(nums[mid]<target)left=mid+1;
else{
//左边界设置为mid，向左寻找左边界
L=mid;
right=mid-1;
}
}
return L;
}
int findR(int *nums,int numsSize,int target){
int left=0,right=numsSize-1,mid,R=-1;
while(left<=right){
mid=left+(right-left)/2;//防止溢出
if(nums[mid]>target)right=mid-1;
else if(nums[mid]<target)left=mid+1;
else{
//右边界设置为mid，向右寻找右边界
R=mid;
left=mid+1;;
}
}
return R;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int *a=malloc(sizeof(int)*2);
a[0]=findL(nums,numsSize,target);
a[1]=findR(nums,numsSize,target);
*returnSize=2;
return a;
}367 有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
1 <= num <= 231 - 1
解题思路：与69x的平方根类似，利用二分法找到num的算数平方根result。如果mid*mid<=num,更新result的值为mid,更新左边界为mid+1
如果result*result=num,返回true，否则，返回false
bool isPerfectSquare(int num) {
long long left=0,right=num,mid,result;
while(left<=right){
mid=(right-left)/2+left;
if(mid*mid<=num){
result=mid;
left=mid+1;
}
else right=mid-1;
}
if(result*result==num)return true;
else return false;
}27 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
解题思路：利用双指针中的快慢指针，slow为数组要更新的位置，初始值为0，fast为数组查找位置，nums[fast]!=val,更新nums[slow]的值。如果nums[fast]==val，fast++,继续向前查找。
int removeElement(int* nums, int numsSize, int val) {
int slow=0,fast=0;
for(fast=0;fast<numsSize;fast++){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}