qidao123.com技术社区-IT企服评测·应用市场

标题: leetcode day17 二分查找 34+367 移除元素27 [打印本页]
作者: 不到断气不罢休    时间: 2025-4-29 20:55
标题: 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4