【LeetCode】0～n-1 中缺失的数字 Java 题解

关注

发布于: 1 小时前

题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。


示例 1:
输入: [0,1,3]输出: 2示例 2:
输入: [0,1,2,3,4,5,6,7,9]输出: 8
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这是排序数组查找元素的题目，对于排序数组，一般使用二分法，效率比较高。
二分查找，每次计算数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
二分查找

代码

    public int missingNumber(int[] nums) {        int n = nums.length;        int left = 0;        int right = n - 1;         while (left <= right) {            int mid = left + (right - left) / 2;            if (nums[mid] == mid) {                left = mid + 1;            } else {                right = mid - 1;            }        }
        return left;    }

复制代码

总结

二分查找解法的时间复杂度是 O(log n), 空间复杂度是 O(1)
二分查找整体思路比较清晰，每一步都要清楚为什么这样写，不要跳步，更不能想当然。需要注意下列几个地方：

while (left <= right)，建议使用左闭右闭区间。
取 int mid = left + (right - left) / 2；为什么这样写？在 left + right 整形溢出的时候，mid 会变成负数，前面的写法可以规避这种问题。
认真分析下一个区间的变化情况，来决定 left, right 的变化条件。

坚持每日一题，加油！

发布于: 1 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/05cdbfa838b5b5da7553e94a3】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】0～n-1 中缺失的数字 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论