一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 555|回复: 18
收起左侧

[数组] Leetcode287. Find the Duplicate Number Follow up

[复制链接] |试试Instant~ |关注本帖
111180611 发表于 2016-5-31 08:14:57 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目:

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O(1) extra space.
  • Your runtime complexity should be less than O(n2).
  • There is only one duplicate number in the array, but it could be repeated more than once.
如果没有限制修改数组,有没有什么其他的算法?


JimmyZhuang 发表于 2016-5-31 08:36:14 | 显示全部楼层
本帖最后由 JimmyZhuang 于 2016-5-31 08:37 编辑

int findDuplicate(vector<int>& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {
      int mid = low + (high - low) / 2;
      int c = 0;
      for(int i = 0; i < nums.size(); i++) {
         if(nums <= mid) c++;
      }
      if(c <= mid)
         low = mid + 1;
      else
         high = mid;
   }
   return nums[low];
}
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-31 10:55:33 | 显示全部楼层
hashmap, first sort then binary search
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-31 10:55:59 | 显示全部楼层
JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

you need to sort first
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-31 11:37:54 | 显示全部楼层
允许修改原数组的话,就用pigeonhole principle直接sort。
O(n) time, O(1) space

  1. int findDuplicate(vector<int>& nums) {

  2.         for(int i=0; i<nums.size(); i++) {
  3.             
  4.             int val = nums[i];
  5.             if(i!=val){
  6.                
  7.                 if(nums[val]==val)
  8.                     return val;
  9.                 swap(nums[val], nums[i]);
  10.                 i--;
  11.             }
  12.             
  13.         }
  14.         
  15.         return -1;
  16.     }
复制代码
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-5-31 14:04:20 | 显示全部楼层

No, I don't need to sort. Take a look at my low and high, they are not indexes.
回复 支持 反对

使用道具 举报

e453079612 发表于 2016-5-31 21:39:55 | 显示全部楼层
JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

二楼最后返回的结果应该是low,不是nums[low]
回复 支持 反对

使用道具 举报

vae371 发表于 2016-5-31 22:37:34 | 显示全部楼层
请问一下,这个不是全都取异或看剩下来的数就行了吗?
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-5-31 23:46:46 | 显示全部楼层
vae371 发表于 2016-5-31 22:37
请问一下,这个不是全都取异或看剩下来的数就行了吗?

那是另外一道题。。这个重复可以重复很多次的。。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-5-31 23:49:12 | 显示全部楼层
答案那个O(n)的做法是把这个看成linkedlist cycle...好难想。。还是binary search那个,判断这个数是否小于当前的mid,比较好想。。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-5-31 23:49:49 | 显示全部楼层
JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

这个应该return low。。。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-5-31 23:50:56 | 显示全部楼层

应该不需要sort吧。。sort了也没错。。因为你是过一遍来判断所有的数里面有多少小于mid的。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-31 23:58:51 | 显示全部楼层
二楼的解法应该是对的,最后返回值写错了。
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-6-1 00:03:05 | 显示全部楼层
e453079612 发表于 2016-5-31 21:39
二楼最后返回的结果应该是low,不是nums[low]

是的,不好意思,习惯打成index了。谢谢纠正哈
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-6-1 00:03:56 | 显示全部楼层
jy_121 发表于 2016-5-31 23:58
二楼的解法应该是对的,最后返回值写错了。

谢谢纠正,对的,返回值是low
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-6-1 02:01:32 | 显示全部楼层
JimmyZhuang 发表于 2016-5-31 08:36
int findDuplicate(vector& nums) {
   int low = 1, high = nums.size() - 1;
   while(low < high) {

为什么low从1开始?
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-6-1 02:18:48 | 显示全部楼层
111180611 发表于 2016-6-1 02:01
为什么low从1开始?

这个low, high不是index,是nums里面的1到n的值,而nums.size()是n + 1
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-6-1 02:25:14 | 显示全部楼层
111180611 发表于 2016-6-1 02:01
为什么low从1开始?

从0开始应该也是对的。。因为不存在length小于2的情况。。
我的java代码这么写的,能过:
public int findDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while (start<end){
            int mid = start+(end-start)/2;
            int count = 0;
            for (int num : nums){
                if (num<=mid) count++;
            }
            if (count>mid) end = mid;
            else start = mid+1;
        }
        return start;
    }
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-6-1 02:29:06 | 显示全部楼层
zpinthehouse 发表于 2016-6-1 02:25
从0开始应该也是对的。。因为不存在length小于2的情况。。
我的java代码这么写的,能过:
public int f ...

嗯,start是0,应该不影响
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表