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为返回数组的巨细。

1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
5.     int left=0,right=numsSize-1,mid,flag=1;//flag=1表示未找到
6.     int *a=malloc(sizeof(int)*2);
7.     while(left<=right&&flag){
8.         mid=left+(right-left)/2;
9.         if(nums[mid]>target)right=mid-1;
10.         else if(nums[mid]<target)left=mid+1;
11.         else flag=0;
12.     }
13.     if(flag) a[0]=-1,a[1]=-1;
14.     else{
15.         int start=mid,end=mid;
16.         for(int i=mid+1;i<numsSize;i++){
17.             if(nums[i]==target)end=i;
18.         }
19.         for(int i=mid-1;i>=0;i--){
20.             if(nums[i]==target)start=i;
21.         }
22.         a[0]=start,a[1]=end;
23.     }
24.     *returnSize=2;
25.     return a;
26. }

复制代码

时间复杂度分析，二分查找部分时间复杂度为 O(log n) ，确定界限时间复杂度为O(n),所以，整个函数时间复杂度为O(n)，不满足题目时间复杂度要求，换一种解法。
解题思路：使用两个函数二分法探求左右界限,初始值为-1
探求左界限findL函数，如果nums[mid]==target,左界限设置为mid，向左探求左界限，故right=mid-1,其他与二分法思路同等。

1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. int findL(int *nums,int numsSize,int target){
5.       int left=0,right=numsSize-1,mid,L=-1;
6.       while(left<=right){
7.         mid=left+(right-left)/2;//防止溢出
8.         if(nums[mid]>target)right=mid-1;
9.         else if(nums[mid]<target)left=mid+1;
10.         else{
11.             //左边界设置为mid，向左寻找左边界
12.             L=mid;
13.             right=mid-1;
14.         }
15.       }
16.       return L;
17. }
18. int findR(int *nums,int numsSize,int target){
19.       int left=0,right=numsSize-1,mid,R=-1;
20.       while(left<=right){
21.         mid=left+(right-left)/2;//防止溢出
22.         if(nums[mid]>target)right=mid-1;
23.         else if(nums[mid]<target)left=mid+1;
24.         else{
25.             //右边界设置为mid，向右寻找右边界
26.             R=mid;
27.             left=mid+1;;
28.         }
29.       }
30.       return R;
31. }
32. int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
33.   
34.     int *a=malloc(sizeof(int)*2);
35.     a[0]=findL(nums,numsSize,target);
36.     a[1]=findR(nums,numsSize,target);
37.     *returnSize=2;
38.     return a;
39. }

复制代码

367 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如  sqrt 。

示例 1：

1. <strong>输入：</strong>num = 16
2. <strong>输出：</strong>true
3. <strong>解释：</strong>返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

复制代码

示例 2：

1. <strong>输入：</strong>num = 14
2. <strong>输出：</strong>false
3. <strong>解释：</strong>返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
4. 1 <= num <= 231 - 1

复制代码

解题思路：与69x的平方根类似，使用二分法找到num的算数平方根result。如果mid*mid<=num,更新result的值为mid,更新左界限为mid+1
如果result*result=num,返回true，否则，返回false

1. bool isPerfectSquare(int num) {
2.     long long left=0,right=num,mid,result;
3.     while(left<=right){
4.         mid=(right-left)/2+left;
5.         if(mid*mid<=num){
6.             result=mid;
7.             left=mid+1;
8.         }
9.         else right=mid-1;
10.     }
11.     if(result*result==num)return true;
12.     else return false;
13. }

复制代码

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++,继续向前查找。

1. int removeElement(int* nums, int numsSize, int val) {
2.     int slow=0,fast=0;
3.     for(fast=0;fast<numsSize;fast++){
4.          if(nums[fast]!=val){
5.             nums[slow]=nums[fast];
6.             slow++;
7.          }
8.     }
9.     return slow;
10. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。