leetcode day17 二分查找 34+367 移除元素27

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;
}