标签：right return target nums int 随想录笔记刷题 left

代码随想录——数组

理论基础

二分查找

704. 二分查找 - 力扣（LeetCode）

代码/思路

在一个有序数组中通过二分查找解决找到目标值的问题。

C++版

//版本一：左闭右闭的写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //定义target在[left,right]闭区间
        int left=0;
        int right = nums.size()-1;
        while(left<=right){
            //防止溢出，等同于(left + right)/2
            int middle = left + ((right-left)/2);
            if(nums[middle]>target){
                // target 在左区间，所以[left, middle - 1]
                right=middle-1;
            }else if(nums[middle]<target){
                // target在右区间，所以[middle + 1, right]
                left=middle+1;
            }else{// nums[middle] == target
                // 数组中找到目标值，直接返回下标
                return middle;
            }
        }
        //未找到目标就返回-1下标
        return -1;
    }
};

//版本二：左闭右开的写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //定义target在[left,right) 左闭右开区间
        int left=0;
        int right = nums.size();
        while(left<right){
            //防止溢出，等同于(left + right)/2
            int middle = left + ((right-left)/2);
            if(nums[middle]>target){
                // target 在左区间，所以[left, middle)
                right=middle;
            }else if(nums[middle]<target){
                // target在右区间，所以[middle + 1, right)
                left=middle+1;
            }else{// nums[middle] == target
                // 数组中找到目标值，直接返回下标
                return middle;
            }
        }
        //未找到目标就返回-1下标
        return -1;
    }
};

Java版

//版本一的写法
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] 或 大于nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

JavaScript版

 //版本一的写法
var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        //注意向下取整，防止变成浮点数
        let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {
            right = mid - 1; 
        } else if (nums[mid] < target) {
            left = mid + 1;   
        } else {
            return mid;
        }
    }
    return -1;
};

时间复杂度

时间复杂度：\(O(\log n)\)，其中 \(n\) 是数组的长度。由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 \(O(\log n)\)，其中 \(n\) 是数组的长度。
空间复杂度：\(O(1)\)。

35. 搜索插入位置

代码/思路

暴力搜索

遍历查找

C++版

//版本一：暴力写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 无非就三种情况：
        // 1. 插入数组所有元素前或所有数组元素的末尾
        // 2. 找到数组中的目标索引
        // 3. 插入到数组的某个位置
        // 因此，先遍历查找
        for(int i=0;i<nums.size();i++){
            // 一旦发现大于或者等于target的num[i]，符合2与3的情况
            if(nums[i]>=target){
                return i;
            }
        }
        //当发现数组未空，或者已经遍历完了，那么返回该数组本身就符合第1种情况
        return nums.size();
    }
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

二分查找

这题的本质其实跟704题一模一样，最终还是可以通过二分查找决定目标值是要在数组中的索引或是应插入的位置。

C++版

//版本二：二分查找的左闭右闭的写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int middle=left+((right-left)/2);
            if (nums[middle] > target) {
                right = middle - 1; 
            } else if (nums[middle] < target) {
                left = middle + 1; 
            } else { 
                return middle;
            }
        }
        // 分为以下四种情况：
        // 1、目标值在数组所有元素之前  [0, -1]
        // 2、目标值等于数组中某一个元素  return middle;
        // 3、目标值插入数组中的位置，return  right + 1
        // 4、目标值在数组所有元素之后的情况,因为是右闭区间，所以 return right + 1
        return right+1;
    }
};
//版本三：二分查找的左闭右开的写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0,right = nums.size(); 
        while (left < right) { 
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; 
            } else if (nums[middle] < target) {
                left = middle + 1; 
            } else { 
                return middle; 
            }
        }
        // 分别为以下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
        return right;
    }
};

Java版

//版本二的写法
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; 
            if (nums[mid] > target) {
                right = mid - 1; 
            } else if (nums[mid] < target) {
                left = mid + 1; 
            } else {
                return mid;
            }
        }
        return right + 1;
    }
}

JavaScript版

//版本二的写法
var searchInsert = function (nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) >> 1);
    if (target > nums[mid]) {
        left = mid + 1;
    } else if(target < nums[mid]){
        right = mid - 1;
    }else{
        return mid;
    }
  }

  return right+1;
};

复杂度分析

时间复杂度：\(O(log n)\)
空间复杂度：\(O(1)\)

34. 在排序数组中查找元素的第一个和最后一个位置

代码/思路

这题采用 \(C++\) 的 \(upper_bound()\) 和 \(lower_bound()\) 就可以找到目标值 \(target\) 在排序数组的开始位置和结束位置，而这两个函数可以用二分查找实现，代码参考《谷歌高畅Leetcode刷题笔记》，具体实现思路其实也可以看leetcode的官方题解。

C++版

//版本一：二分查找
class Solution {
private:
//这里采用左闭右闭的写法，upper_bound()与lower_bound()的唯一不同之处在于
//要令upper指向最后一位就令nums[mid]>target而不是像lower一样令nums[mid]>=target
    int lower_bound(vector<int> &nums,int target){
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }

    int upper_bound(vector<int> &nums,int target){
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //如果一开始的数组为空是无效的
        if(nums.empty()) return vector<int>{-1,-1};
        int lower=lower_bound(nums,target);
        //这里要减一
        int upper=upper_bound(nums,target)-1;
        //如果开始位置已经到了末尾或者根本不等于我们的目标值就是无效的
        if(lower==nums.size() || nums[lower]!=target){
            return vector<int>{-1,-1};
        }
        return vector<int>{lower,upper};
    }
};

Java版

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //根据之前的C++的代码内容，就可以知道upper_bound()和lower_bound()怎么写在一起，但是要注意之前的判断条件其实也要跟着变得如下严谨
        int lowerIndex = binarySearch(nums, target, true);
        int upperIndex = binarySearch(nums, target, false) - 1;
        //在保证lower的下标要小于upper的下标 与 upper的下标不超过nums数组的长度的情况下，再确认upper与lower值是否跟target相同，
        if (lowerIndex <= upperIndex && upperIndex < nums.length && nums[lowerIndex] == target && nums[upperIndex] == target) {
            return new int[]{lowerIndex, upperIndex};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean be_lower) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //不用担心溢出
            int mid = (left + right) / 2;
            if (nums[mid] > target || (be_lower && nums[mid] >= target)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

JavaScript版

const binarySearch = (nums, target, be_lower) => {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        //向下取整
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (be_lower && nums[mid] >= target)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

var searchRange = function(nums, target) {
    let ans = [-1, -1];
    const lowerIndex = binarySearch(nums, target, true);
    const upperIndex = binarySearch(nums, target, false) - 1;
    if (lowerIndex <= upperIndex && upperIndex < nums.length && nums[lowerIndex] === target && nums[upperIndex] === target) {
        ans = [lowerIndex, upperIndex];
    } 
    return ans;
};

Python版

class Solution(object):
    def searchRange(self, nums, target):
        # 这题的含义类似于C++的lower_bound 和 upper_bound 函数，具体的函数的实现，可以通过二分查找
        def lower_bound(nums,target):
            left=0;right=len(nums)
            while left<right:
                mid=left+(right-left)/2
                if nums[mid]>=target:
                    right=mid
                else:
                    left=mid+1
            return left
            
        def upper_bound(nums,target):
            left=0;right=len(nums)
            while left<right:
                mid=left+(right-left)/2
                if nums[mid]>target:
                    right=mid
                else:
                    left=mid+1
            return left
        if len(nums)==0:return [-1,-1]
        lower=lower_bound(nums,target)
        # 这里需要减一位，因为得到的值的下标会溢出
        upper=upper_bound(nums,target)-1
        if lower==len(nums) or nums[lower]!=target:
            return [-1,-1]
        return [lower,upper]

复杂度分析

时间复杂度：\(O(\log n)\) ，其中 \(n\) 为数组的长度。二分查找的时间复杂度为 \(O(\log n)\)，一共会执行两次，因此总时间复杂度为 \(O(\log n)\)。
空间复杂度：\(O(1)\)

69. x 的平方根

代码/思路

这题就是给你一个值，然后求它的算术平方根，一般人的思路也许就是硬算，就跟自己的朋友学数学一样（声明：这个朋友不是我），或者投机取巧用已有的轮子。

其实这题也可以使用二分查找，因为我们可以设置\([1,x]\)的区间（当然要注意\(x\)为\(0\)的情况），在二分查找该区间要的数值\(sqrt\)的过程中，其实令值\(x\)除以中间值\(mid\)，再跟\(sqrt\)一一比较判断即可。

C++版

//版本一：二分查找
class Solution {
public:
    int mySqrt(int x) {
        if(x==0)return x;
        int left=1,right=x;
        while(left<=right){
            int mid=left+(right-left)/2;
            int sqrt=x/mid;
            if(mid == sqrt) return mid;
            else if (mid>sqrt) right=mid-1;
            else left=mid+1;
        }
        return right;
    }
};

Java版

class Solution {
    public int mySqrt(int x) {
        int left=0,right=x,result=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if((long) mid*mid<=x){
                result=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return result;
    }
}

JavaScript版

var mySqrt = function(x) {
    let left=0,right=x,result=-1;
    while(left<=right){
        let mid=Math.floor((left+right)/2);
        if(mid*mid<=x){
            result=mid;
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return  result;
};

Python版

class Solution(object):
    def mySqrt(self, x):
        # 这里单独拿出0的情况分析
        if x==0:return x
        left=1;right=x
        while left<=right:
            mid=left+(right-left)/2
            sqrt=x/mid # mid*mid=x
            if mid==sqrt:
                return mid
            elif mid>sqrt:
                right=mid-1
            else:
                left=mid+1
        return right

复杂度分析

时间复杂度：\(O(\log x)\) 。
空间复杂度：\(O(1)\)。

另外跟着leetcode写袖珍计算器算法，牛顿迭代法。

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 \(\exp\) 和对数函数 \(\ln\) 代替平方根函数的方法。

我们将 \(\sqrt{x}\)写成幂的形式 \(x^{1/2}\) ，再使用自然对数 \(e\) 进行换底，即可得到

\[\sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x} \]

这样我们就可以得到 \(\sqrt{x}\) 的值了。

C++版

class Solution {
public:
    int mySqrt(int x) {
        //单独拿0出来处理
        if(x==0){
            return 0;
        }
        //经过转换的公式
        int ans=exp(0.5*log(x));
        //由于计算机无法存储浮点数的精确值，会有整数1的相差，所以要对 ans 与 ans+1 进行判断
        return ((long long)(ans+1)*(ans+1)<=x ?  ans+1:ans);    
    }
};

复杂度分析

时间复杂度：\(O(1)\)，由于内置的 \(exp\) 函数与 \(log\) 函数一般都很快，我们在这里将其复杂度视为 \(O(1)\)。
空间复杂度：\(O(1)\)。

牛顿迭代法

这理论把我看到吐了，让我想起自己不自量力地参加数学建模竞赛的那些日子。

牛顿迭代法的本质是借助泰勒级数，根据高等数学的内容，解答给的是二阶泰勒公式\(y=f(x)=x^2−C\)

以我们高中熟悉的斜线方程\(y-y_i=k(x-x_i)+b\)为例，其中斜率\(k\)为\(f(x)\)的导数。

由于选择 \(x_0=C\) 作为初始值，找点 \((x_i, x_i^2 - C)\) 作直线，之后经过转换，求的\(x\)值就成为了新的迭代结果\(x_{i+1}\)。

也即leetcode官方解答的

\[x_{i+1} = \frac{1}{2}\left(x_i + \frac{C}{x_i}\right) \]

C++版

class Solution {
public:
    int mySqrt(int x) {
        //单独拿0出来处理
        if(x==0){
            return 0;
        }
        //C表示待求出平方根的那个整数，而又选择 x_0 = C 作为初始值
        double C=x,x0=x;
        while(true){
            double xi=0.5*(x0+C/x0);
            //设立极限值
            if(fabs(x0-xi)<1e-7){
                break;
            }
            //迭代递进
            x0=xi;
        }
        //向下取整
        return int(x0);
    }
};

复杂度分析

时间复杂度：\(O(\log x)\) ，此方法是二次收敛的，相较于二分查找更快。
空间复杂度：\(O(1)\)。

367. 有效的完全平方数

代码/思路

这题如果采用暴力的写法，其实就是遍历\([1,完全平方数]\)的区间，一个一个算。

那么清楚暴力的方法后，就可以通过二分查找去缩短查找耗时。

当然其实也可以用牛顿迭代法，具体的实现步骤其实跟上一题一致，只不过由于这题的结果为布尔值，所以代码上特别处理。

C++版

//版本一：暴力写法
class Solution {
public:
    bool isPerfectSquare(int num) {
        //要防溢出，用long
        long x=1,square=1;
        while(square<=num){
            if(square==num){
                return true;
            }
            //遍历
            ++x;
            square=x*x;
        }
        //遍历完都没找到
        return false;
    }
};

//版本二：二分查找
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=0,right=num;
        while(left<=right){
            int mid=left+(right-left)/2;
            long square=(long) mid*mid;
            if(square<num){
                left=mid+1;
            }else if(square > num){
                right=mid-1;
            }else{
                return true;
            }
        }
        return false;
    }
};

//版本三：牛顿迭代法
class Solution {
public:
    bool isPerfectSquare(int num) {
        int C=num;
        double x0=num;
        while(true){
            double xi=0.5*(x0+C/x0);
            //不给用函数fabs，这里求极限值
            if(x0-xi<1e-6){
                break;
            }
            x0=xi;
        }
        int x=(int) x0;
        //判断
        return x * x == num;
    }
};

Java版

//版本二的写法
class Solution {
    public boolean isPerfectSquare(int num) {
        int left=0,right=num;
        while(left<=right){
            int mid=left+(right-left)/2;
            long square=(long) mid*mid;
            if(square<num){
                left=mid+1;
            }else if(square > num){
                right=mid-1;
            }else{
                return true;
            }
        }
        return false;

    }
}

JavaScript版

//版本二的写法
var isPerfectSquare = function(num) {
    let left=0,right=num;
    while(left<=right){
        let mid=Math.floor((left+right)/2);
        let square=mid*mid;
        if(square<num){
            left=mid+1;
        }else if(square>num){
            right=mid-1;
        }else{
            return true;
        }
    }
    return false;
};

如果是暴力

时间复杂度：\(O(\sqrt{n})\)，其中 \(n\) 为正整数 \(\textit{num}\)的最大值。我们最多需要遍历 \(\sqrt{n} + 1\)
空间复杂度：\(O(1)\)。

如果是二分查找或者牛顿迭代的话

复杂度分析

时间复杂度：\(O(\log n)\) 。
空间复杂度：\(O(1)\)。

双指针——左右、快慢

27. 移除元素

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

283. 移动零

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

844. 比较含退格的字符串

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

977. 有序数组的平方

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

滑动窗口

209. 长度最小的子数组

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

904. 水果成篮

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

76. 最小覆盖子串

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

模拟

59. 螺旋矩阵 II

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

54. 螺旋矩阵

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

剑指 Offer 29. 顺时针打印矩阵

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

总结

标签：right,return,target,nums,int,随想录,笔记,刷题,left
From： https://www.cnblogs.com/PaturNax/p/16591375.html

【代码随想录刷题笔记】——数组（持续更新中）

代码随想录——数组

二分查找

代码/思路

时间复杂度

代码/思路

暴力搜索

复杂度分析

二分查找

复杂度分析

代码/思路

复杂度分析

代码/思路

复杂度分析

袖珍计算器算法

复杂度分析

牛顿迭代法

复杂度分析

代码/思路

复杂度分析

双指针——左右、快慢

滑动窗口

模拟

总结

相关文章

赞助商

阅读排行