本文共 4843 字，大约阅读时间需要 16 分钟。

二分法

1、题目地址(69. x 的平方根)

https://leetcode-cn.com/problems/sqrtx/

题目描述

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。示例 1:输入: 4输出: 2示例 2:输入: 8输出: 2说明: 8 的平方根是 2.82842...,      由于返回类型是整数，小数部分将被舍去。

代码

• 语言支持：Java

Java Code:

class Solution {    public int mySqrt3(int x) {        int l = 0, r = x, ans = -1;        while (l <= r) {            int mid = l + (r - l) / 2;            if ((long) mid * mid <= x) {                ans = mid;                l = mid + 1;            } else {                r = mid - 1;            }        }        return ans;    }    public int mySqrt2(int x) {        if( x <= 1){            return x;        }        int left = 1;        int right = x;        int mid = left + ((right - left)>>1);        while(left <= right){            if( (long)mid*mid > x ){                right = mid - 1;                mid = left + ((right - left)>>1);            }            else if ( (long)mid*mid < x ){                left = mid + 1;                mid = left + ((right - left)>>1);                   }            else{                return mid;            }        }        return mid;    }    public int mySqrt(int x) {        if( x <= 1){            return x;        }        for(long i=0; i<=x-1; i++){            if( i*i <= x && (i+1)*(i+1) > x ){                return (int)i;            }        }        return 1;    }}

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

2、题目地址(374. 猜数字大小)

https://leetcode-cn.com/problems/guess-number-higher-or-lower/

题目描述

猜数字游戏的规则如下：每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：-1：我选出的数字比你猜的数字小 pick < num1：我选出的数字比你猜的数字大 pick > num0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num返回我选出的数字。 示例 1：输入：n = 10, pick = 6输出：6示例 2：输入：n = 1, pick = 1输出：1示例 3：输入：n = 2, pick = 1输出：1示例 4：输入：n = 2, pick = 2输出：2 提示：1 <= n <= 231 - 11 <= pick <= n

代码

• 语言支持：Java

Java Code:

/**  * Forward declaration of guess API. * @param  num   your guess * @return 	     -1 if num is lower than the guess number *			      1 if num is higher than the guess number *               otherwise return 0 * int guess(int num); */public class Solution extends GuessGame {    public int guessNumber(int n) {        int left = 1, right = n,  mid = left + ((right - left)>>1);        while(left <= right){            if( guess(mid) == 1 ){                left = mid + 1;                mid = left + ((right - left)>>1);            }            else if( guess(mid) == -1 )            {                right = mid - 1;                mid = left + ((right - left)>>1);            }            else{                return mid;            }        }        return mid;    }}

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

3、有序矩阵中第 K 小的元素

[https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/]

题目描述

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。 示例 1：输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8输出：13解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13示例 2：输入：matrix = [[-5]], k = 1输出：-5 提示：n == matrix.lengthn == matrix[i].length1 <= n <= 300-109 <= matrix[i][j] <= 109题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列1 <= k <= n2

思路

代码

• 语言支持：Java

Java Code:

class Solution {    public int kthSmallest(int[][] matrix, int k) {        int left = matrix[0][0];        int n = matrix.length;        int right = matrix[n-1][n-1];                while( left < right ){            int num = 0;            int mid = ( left + right ) / 2;            // 开始统计 小于等于mid 的数量            for(int i=0; i
   
    =0; j--){                    if( matrix[j][i] <= mid){                        num += (j+1);                        break;                    }                }            }            // 统计完 小于等于mid 的数量             if( num >= k ){                // 缩小范围                right = mid;            }            else{                // num小于k  要增大范围，就是增大mid，所以要增加left+right的值，增大left即可                left = mid + 1;// 不加1的话，如果左右是11 13，答案正好是12的话，那不是一直在这循环了            }        }        return right;    }    public int kthSmallest2(int[][] matrix, int k) {        int n = matrix.length;        int left = matrix[0][0];        int right = matrix[n - 1][n - 1];        while (left < right) {            int mid = left + ((right - left) >> 1);            if (check(matrix, mid, k, n)) {                right = mid;            } else {                left = mid + 1;            }        }        return left;    }    public boolean check(int[][] matrix, int mid, int k, int n) {        int i = n - 1;        int j = 0;        int num = 0;        while (i >= 0 && j < n) {            if (matrix[i][j] <= mid) {                num += i + 1;                j++;            } else {                i--;            }        }        return num >= k;    }}
   

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

转载地址：https://blog.csdn.net/qq_39555841/article/details/117409176 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！