跳至内容

有效的完全平方数

LeetCode 367：用二分查找判断是否存在平方恰好等于 num 的整数。

LeetCode 367 简单 数组
发布于 约 3 分钟阅读 浏览 — 次
  • 二分查找
  • 数学
  • 复杂度
  • Python
  • 变量

题目：367. 有效的完全平方数

给你一个正整数 num。如果 num 是一个 完全平方数，则返回 true，否则返回 false。

完全平方数是可以写成某个整数与自身乘积的整数，例如 16 = 4 * 4。

注意： 不能使用任何内置的库函数，如 sqrt。

示例 1：

  • 输入： num = 16
  • 输出： true
  • 解释： 4 * 4 = 16，且 4 是整数。

示例 2：

  • 输入： num = 14
  • 输出： false
  • 解释： 3 * 3 = 9 < 14 < 16 = 4 * 4，没有整数的平方恰好等于 14。

1. 查找过程

要找的是 平方恰好等于 num 的整数。非负整数越大，平方越大，可以用二分查找缩小范围。

下面是区间示意：k 表示候选整数，k² 表示它的平方；L、M、R 对应代码中的 l、mid、r。

1.1 找到整数平方根：num = 16

第 1 轮：检查 [0, 15]

代码块 Text
1
2
3
4

k:    0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
k²:   0   1   4   9  16  25  36  49  64  81 100 121 144 169 196 225
      ●───●───●───●───●───●───●───●───●───●───●───●───●───●───●───●
      L                           M                               R

mid = 7，7 * 7 = 49 > 16。7 已经太大，右侧的数也都太大。

更新 r = mid - 1，得到 r = 6，剩下 [0, 6]。

第 2 轮：检查 [0, 6]

代码块 Text
1
2
3
4

k:    0   1   2   3   4   5   6
k²:   0   1   4   9  16  25  36
      ●───●───●───●───●───●───●
      L           M           R

mid = 3，3 * 3 = 9 < 16。3 太小，左侧的数也都太小。

更新 l = mid + 1，得到 l = 4，剩下 [4, 6]。

第 3 轮：检查 [4, 6]

代码块 Text
1
2
3
4

k:    4   5   6
k²:  16  25  36
      ●───●───●
      L   M   R

mid = 5，5 * 5 = 25 > 16，排除 5 和 6。

更新 r = mid - 1，得到 r = 4，只剩 4。

第 4 轮：只检查整数 4

代码块 Text
1
2
3
4

k:    4
k²:  16
      ●
    L=M=R

mid = 4，4 * 4 == 16，找到满足条件的整数，直接返回 True。

1.2 没有整数平方根：num = 14

同样从 [0, num - 1] 开始，逐轮变化如下：

本轮区间 [l, r]mid平方比较更新边界
[0, 13]636 > 14r = 5
[0, 5]24 < 14l = 3
[3, 5]416 > 14r = 3
[3, 3]39 < 14l = 4

最后 l = 4 > r = 3，区间已空。所有可能值都被排除，没有一次平方恰好等于 14，返回 False。

2. Python 实现

当 num >= 2 时，若存在整数平方根，它一定小于 num，所以右边界可以取 num - 1。

代码块 Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def is_perfect_square(num):
    # 本题输入为正整数，num < 2 只会是 1，且 1 * 1 = 1
    # 若不单独处理 1，初始右边界需改为 num，否则会漏掉答案 1
    if num < 2:
        return True

    l, r = 0, num - 1  # 左闭右闭区间 [l, r]
    while l <= r:
        mid = l + (r - l) // 2
        if mid * mid == num:
            return True  # 找到整数 mid，其平方恰好等于 num
        elif mid * mid > num:
            r = mid - 1  # mid 及其右侧整数的平方都太大
        else:  # mid * mid < num
            l = mid + 1  # mid 及其左侧整数的平方都太小
    return False  # 区间已空，没有找到平方等于 num 的整数


print(is_perfect_square(16))
print(is_perfect_square(14))
print(is_perfect_square(9))
print(is_perfect_square(1))
运行结果 Text
1
2
3
4

# True
# False
# True
# True

3. 复杂度

  • 时间复杂度：O(log num)，每轮将整数候选区间缩小约一半。
  • 额外空间复杂度：O(1)，只维护固定数量的整数变量。

评论

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。