Leetcode 题目解析:287. 寻找重复数
系列文章:
一 摘要
基于数组的运算,是面试算法题中很大的一部分题目。很多问题的输入,都可以以数组的形式给出,所以,我们对数组特性、常见题目的掌握程度,就直接决定了我们对相关算法的解决能力。
遍历、排序、二分...这些都是在解决具体问题时常用的手段;作为辅助,也可能有双指针、数组作为循环队列等场景。本篇要解析的这道重复数字寻找,也是其中一个典型的题目。
二 题目描述
引用leetcode的描述原文如下:
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
三 题目解析
3.1 示例
3.2 解析
3.2.1 排序与哈希
判断一个数字是否重复并不难,比较容易想到的就是排序和哈希;分别利用数字的大小,和 map 存储并判断 contains()方法值的真假来确定是否有重复。但这道题要求不修改数组,并且只用常量级 O(1)的额外空间,也就是说,空间复杂度必须是 O(1),那么哈希的方法就不符合了。
再看排序,基于比较排序,只用一个临时变量来实现数字的位置交换,是可行的;再得到排序结果之后,我们再比较相邻的两个数字看是否相同;那么这种方法最好的时间复杂度是 O(nlogn)。那么是否有更好的办法呢?
3.2.2 二分
排序的目的是想通过相邻数字比较来判断是否重复,但实际上,我们并不需要对所有数字进行排序。考虑到 top n 元素的查找方法,是否可以也利用二分法来实现呢?
数组本身无序,所以我们不能直接对数组 nums 本身进行二分;但我们可以对坐标数组{0,1,2,...,n-1}进行二分搜索。当然,对比的不是元素本身,而是小于或等于某个数字的元素个数。
思路:先猜一个数(有效范围 [left..right] 里位于中间的数 mid),然后统计原始数组中 小于等于 mid 的元素的个数 cnt:
如果 cnt 严格大于 mid。根据抽屉原理,重复元素就在区间 [left..mid] 里;
否则,重复元素就在区间 [mid + 1..right] 里。
与绝大多数使用二分查找问题不同的是,这道题正向思考是容易的,即:思考哪边区间存在重复数是容易的,因为有抽屉原理做保证。
3.2.3 代码
版权声明: 本文为 InfoQ 作者【程序员架构进阶】的原创文章。
原文链接:【http://xie.infoq.cn/article/0adffb6423945ec534485bde4】。文章转载请联系作者。
评论