hedvig电面 至今不知怎么解。。

上来就问题目，一道简单的秒过。然后问了一道到现在我都没想到解法的。。

题目：有n+1个1到n的数字，找出重复的字符。
可能有多个字符重复,找出其中任意一个就可以。每个字符可能重复2遍以上。
read only，O(1) extra space.

我回答了O(n^2)的brute force解法。然后实在想不到更快的方法了。
要hint他问最快解法是多少，我说O(n）,他说中间的呢，我说O(n log n), 他说那就找个O(n log n) 的解法出来。。。

当时想到的解法：

• sort，不行，因为是read only
• hash，不行，因为O(1) spa
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  
  
  

开始怀疑自己智商了。。


面试期间还能听到对面有人在讲话在笑，面试官还离开了一会>.< 现在想到电面都腿抽筋=。=

http://cyukang.com/2012/04/11/fi ... ycle-detection.html

mingycool 发表于 2015-8-16 11:56
他家就是奇葩啊，之前电面问我怎么压缩空间存储一个sorted array，既不是算法，也不是数据结构，而且就剩20 ...

这种题没有标准答案，给你1年有1年的答法，20分钟有20分钟的答法。20分钟的话，就是看你能不能在短时间内发散思维，把以前学的东西瞬间应用在新场合上。
假设数组是32位int型数据，我能马上想到的方法有这些：
1.是用一个hashmap: {value->occurrence}来表示这个数组，相当于Run-length压缩法。这最适用于数组有大量重复数据的情况。如果没有重复数据，反而所用内存会变为原来的2倍。
2.是范围表示：比如[1 2 3 4 5 7 8 9 11 13]可以表示为[{1 5}, {7 9}, {11}, {13}],这适用于数据没有重复，但有大量连续的情况。
3.是类似于1和2的综合。先假设我们有一个大小是INT_MAX-INT_MIN的数组M，其中M[i]表示数字i在原数组A中出现的次数。比如当A = [1 2 2 3 4 5 5 7 8 9 11 11 13]时，M = [0 0 0 ..... 0 0 0 1 2 1 1 2 0 1 1 1 0 1 0 1 0 0 0 ... ]，然后用Run-length法再压缩一次M。这个方法比1的好处是当大部分数字都不重复的话，也能获得较高的压缩率。
4. 比3再进一步。如果M中大部分值都是0或1。可以把这些数每32位一组pack到一个int中去。

补充内容 (2015-8-16 12:47):
请自行在斜体开始的地方脑补一个[ i ]，我每次都忘记这件事。

楼主，你看这样行不行。就是很像用leetcode那道find first missing positive题目的解法。因为你确定了array里面的number全部都是［ 1到 n+1］之间的。
所以遍历数组：若当前index下的数字等于index ＋ 1， 则说明在当前所应该在的位置。遍历下一个数字。
                       若不等于，则去找到index ＝ number－1的位置，index ＝ number － 1的位置上，数字等于number，则说明，重复，则返回这个数字。
                      不重复则swap两个数。再进行比较。

1. int getDuplicateNumber(vector<int> nums)
   
2. {
   
3.     int i = 0;
   
4.     while(i < nums.size())
   
5.     {
   
6.         int number = nums[i];
   
7.         if(number == i+1)
   
8.         {
   
9.             i++;
   
10.         }
    
11.         else
    
12.         {
    
13.             if(number == nums[number-1])
    
14.             {
    
15.                 return number;
    
16.             }
    
17.             else
    
18.             {
    
19.                 //swap nums[i] and nums[number];
    
20.                 int tmp = nums[number-1];
    
21.                 nums[number-1] = number;
    
22.                 nums[i] = tmp;
    
23.             }
    
24.         }
    
25.     }
    
26.     return -1;
    
27. }
    

复制代码

补充内容 (2015-8-16 00:58):
好吧。好像不行。因为readonly。。。sorry

你想的Linked List Find Cycle方法应该是可以的：把array中的每一个元素的值看做是其指向的下一个元素的下标（1-based）。那么从最后一个元素开始遍历而形成的链表中一定有环，而且环的开始位置的下标就是重复元素。

比如[3 1 2 1 4]这个数组，从最后一个数4开始，得到的链表是4 -> (4号位上的)1 -> 3 -> 2 -> (2号位上的)1 -> 3 -> .... 环的开头是3，那么3的所在位置的下标一定是重复元素的值。为什么？因为既然它能成为环的开始，说明环外一定有一个元素指向它，而环里也一定有一个元素指向它。

-----

分治法通常都是递归实现的，不用递归的话，通常要自己开辟内存维护当前所分区域的信息。所以恐怕O(NlogN)的算法你就算想出来了，也不满足O(1)memory这个限制条件。

stellari 发表于 2015-8-15 14:49
你想的Linked List Find Cycle方法应该是可以的：把array中的每一个元素的值看做是其指向的下一个元素的下 ...

谢大神回复！完全没想到是环开始的下标，一直在想环里的值。豁然开朗，谢谢大神~
分治法那个是说没有O(nlogn)的解法么？那为什么他会提示我找O(nlogn)的解呢。。。

starriver 发表于 2015-8-15 20:22
谢大神回复！完全没想到是环开始的下标，一直在想环里的值。豁然开朗，谢谢大神~
分治法那个是说没有O(n ...

千万别这么称呼我啊，我水平非常有限……我只是觉得分治法不太容易做到O(1)内存。但是，O(NlogN)的算法并非只有分治法一种，也许有其他的O(NlogN)算法可以解决这道题。只是我目前还没想到。

stellari 发表于 2015-8-15 14:49
你想的Linked List Find Cycle方法应该是可以的：把array中的每一个元素的值看做是其指向的下一个元素的下 ...

好难懂， 还有没有别的方法

补充内容 (2015-8-15 22:47):
好像有点理解了，那这个复杂度是O(n)吗

补充内容 (2015-8-15 22:50):
好像有点理解了，那这个算法的复杂度是不是O(n)

stellari 发表于 2015-8-15 14:49
你想的Linked List Find Cycle方法应该是可以的：把array中的每一个元素的值看做是其指向的下一个元素的下 ...

O(1) space的话怎么判断一个元素有没有被visit过呢？

wenqiang88 发表于 2015-8-15 23:26
O(1) space的话怎么判断一个元素有没有被visit过呢？

不需要判断每个元素是否被visit过，用快慢指针法即可。

我觉得第二题不太可能吧...read only 和space o1 就意味着不能记录访问信息.
所以只能用bit操作.然而出现次数又不定.....

agneshanlu 发表于 2015-8-16 00:56
楼主，你看这样行不行。就是很像用leetcode那道find first missing positive题目的解法。因为你确定了array ...

如果不是read only, 这个题是google onsite的一道经典原题, 就是用负数记录visit的信息 - -