一亩三分地论坛

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

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

[算法题] 寻找出现2次的数

[复制链接] |试试Instant~ |关注本帖
LBS 发表于 2016-3-2 02:15:49 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 LBS 于 2016-3-2 05:39 编辑

给你一个数组,很大,但内存装得下。
已知数组中的数字是(1-n) n是最大数。每个数至少出现一次,但有其中的部分数出现了2次。数组没有排过序。

求出这些出现过两次的数,要求o(1)space,o(n)时间。
例子:

[3,2,2,1,3,4]  告诉你1-4和这个数组, 要求 返回[2,3]。
--------------------------------------------------------------
1:39pm/3/1/2016:
Add one more requirement: you can not change the original  num array



本帖被以下淘专辑推荐:

stellari 发表于 2016-3-2 15:02:37 | 显示全部楼层
这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续,所以完全可以用一个长度为n的Boolean数组代替之。如果要求O(1)空间,把这个Boolean数组挤进原数组前n个数的符号位中即可。如果要求最终结果是“不改变原数组中的值”,那再扫一遍把负数都反过来即可:
  1.        
  2. public static List<Integer> getDup(Integer[] num, int n) {
  3.                 List<Integer> res = new ArrayList<Integer>();
  4.                 for(int i = 0; i < num.length; ++i) {
  5.                         int j = Math.abs(num[i]);   // 找到这个数字应该出现的位置
  6.                         if (num[j-1] < 0) res.add(j);  // 如果这个数字已经出现过一次,则加入结果
  7.                         else num[j-1] = -num[j-1];  // 否则,标记为“已出现”
  8.                 }
  9.                 for (int i = 0; i < n; ++i) { // 恢复原数组
  10.                         if (num[i] < 0) num[i] = -num[i];
  11.                 }
  12.                 return res;
  13.         }
复制代码
回复 支持 2 反对 0

使用道具 举报

staycrazy 发表于 2016-3-3 03:38:46 | 显示全部楼层
fish444555 发表于 2016-3-2 05:29
确实引用可以避免重新开辟空间,谢谢提醒。至于不能改变原来的数组而实现 O(1) space & O(n) complexity ...

其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果并不要求精确匹配,这道题目是bloom filter的原型。
回复 支持 1 反对 0

使用道具 举报

fish444555 发表于 2016-3-2 05:03:00 | 显示全部楼层
之前忽略了 find 的复杂度,SB了,如果插入过的位置标记为负数,这样就可以不用 find

  1. vector<int> Solution::tt(vector<int> nums, int n) {
  2.     vector<int> res;
  3.     if (nums.empty())
  4.             return res;
  5.     for (int i = 0; i < nums.size(); )
  6.     {        
  7.         if (i != nums[i]-1) {
  8.             if (nums[i] == nums[nums[i]-1] || nums[nums[i]-1] == -1) {
  9.                     if (nums[nums[i]-1] != -1) {
  10.                         res.push_back(nums[i]);
  11.                         nums[i] = -1;
  12.                     }
  13.                 i++;
  14.             }
  15.             else {
  16.                 swap(nums[i], nums[nums[i]-1]);
  17.             }            
  18.             continue;
  19.         }
  20.         i++;
  21.     }
  22.     return res;
  23. }
复制代码


只测试了,
vector<int> num1 = {3,2,2,1,3,7,4,4,5,6,7};
vector<int> num1 = {3,2,2,1,3,4};
不知道其它例子有没有bug
回复 支持 1 反对 0

使用道具 举报

Hammy 发表于 2016-3-2 04:16:13 | 显示全部楼层
fish444555 发表于 2016-3-2 03:53
代码大概思想是 数组中数字-1 与下标一一对应, 如果出现多个对应,就是重复数字。如果有bug请指出。sp ...

这个不是O(1)space 吧
回复 支持 1 反对 0

使用道具 举报

fish444555 发表于 2016-3-2 03:53:01 | 显示全部楼层
  1. vector<int> Solution::tt(vector<int> nums, int n) {
  2.     vector<int> res;
  3.     if (nums.empty())
  4.             return res;
  5.     for (int i = 0; i < nums.size(); )
  6.     {        
  7.         if (i != nums[i]-1) {
  8.             if (nums[i] == nums[nums[i]-1] ) {
  9.                     if (find(res.begin(), res.end(), nums[i]) == res.end()) {
  10.                         res.push_back(nums[i]);
  11.                     }
  12.                 i++;
  13.             }
  14.             else {
  15.                 swap(nums[i], nums[nums[i]-1]);
  16.             }            
  17.             continue;
  18.         }
  19.         i++;
  20.     }
  21.     return res;
  22. }
复制代码


代码大概思想是 数组中数字-1 与下标一一对应, 如果出现多个对应,就是重复数字。如果有bug请指出。space O(1), complex O(n)
回复 支持 反对

使用道具 举报

fish444555 发表于 2016-3-2 04:25:04 | 显示全部楼层
Hammy 发表于 2016-3-2 04:16
这个不是O(1)space 吧

我只是对它本来的vector 之间 swap , 没有申请额外的空间啊,space 怎么不是 O(1) , 请指教
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-2 04:38:15 | 显示全部楼层
fish444555 发表于 2016-3-2 03:53
代码大概思想是 数组中数字-1 与下标一一对应, 如果出现多个对应,就是重复数字。如果有bug请指出。sp ...

Thanks for sharing your algorithm, it's really a good idea. And I think your algorithm works. I agree it use a o(1) space. How about the time complexity, if (find(res.begin(), res.end(), nums) == res.end()) I guess find() operation is o(n) runtime? so total runtime gonna be o(n2)?
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-2 04:38:54 | 显示全部楼层
Hammy 发表于 2016-3-2 04:16
这个不是O(1)space 吧

I think it's o(1) space
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-2 05:24:02 | 显示全部楼层
fish444555 发表于 2016-3-2 05:03
之前忽略了 find 的复杂度,SB了,如果插入过的位置标记为负数,这样就可以不用 find

OK! Thank you.

If the problem has more requirements. That the input vector nums will be reused in the future. And we don't want change the nums. Do you have any other way to solve it?

P.S.  I guess  "vector<int> Solution::tt(vector<int> nums, int n) {" should be "vector<int> Solution::tt(vector<int> & nums, int n) {" ? As reference will not create any space.
回复 支持 反对

使用道具 举报

fish444555 发表于 2016-3-2 05:29:59 | 显示全部楼层
LBS 发表于 2016-3-2 05:24
OK! Thank you.

If the problem has more requirements. That the input vector nums will be reused ...

确实引用可以避免重新开辟空间,谢谢提醒。至于不能改变原来的数组而实现 O(1) space & O(n) complexity。 我暂时没有头绪,可能只能等待大神们的解答..........
回复 支持 反对

使用道具 举报

Zestinc 发表于 2016-3-2 18:23:44 | 显示全部楼层
stellari 发表于 2016-3-2 15:02
这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续,所 ...

符号位还能这么用,长经验了
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-4 02:26:58 | 显示全部楼层
stellari 发表于 2016-3-2 15:02
这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续,所 ...

多谢分享!这个负数反过来确实很妙!
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-4 02:30:21 | 显示全部楼层
staycrazy 发表于 2016-3-3 03:38
其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果 ...

面试官最后要希望我延用我之前bit的思想解这题,我只想出了一个最简单的想法,就是用n/32 个 32bit的数表示(这样并不是constant space),如此操作,每一位就是代表一个容器。 我再回顾一下bloom filter ,多谢。
回复 支持 反对

使用道具 举报

 楼主| LBS 发表于 2016-3-5 08:48:10 | 显示全部楼层
staycrazy 发表于 2016-3-3 03:38
其实使用符号位挺作弊的,相当于使用了1/word的额外空间——万一人家数组是无符号的byte怎么办?

如果 ...

你好,能请教一下此题如何套用bloom filter吗?
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-5 10:12:15 | 显示全部楼层
我觉得楼上强行占用原数组空间的方法不太好,因为这假设了原数组必须是用int储存的,如果用uint怎么办?
另外关于bloom filter的方法,我觉得额外开常数空间是不太可行的。(应该说显然是不可行的,因为常数空间能标示的状态数也就是常数)
不过一般这种题目说是哦o(1),大多是o(logn),否则连counter都开不起。
回复 支持 反对

使用道具 举报

lefttree 发表于 2016-3-5 16:56:54 | 显示全部楼层
LBS 发表于 2016-3-4 02:30
面试官最后要希望我延用我之前bit的思想解这题,我只想出了一个最简单的想法,就是用n/32 个 32bit的数表 ...

那面试官的意思应该是用bitmap,因为之前已经告诉了范围是1-n, 每一位bit代表一个数字,每出现一次就xor, 最后是0的应该就是出现两次的数。
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-5 18:12:43 | 显示全部楼层
lefttree 发表于 2016-3-5 16:56
那面试官的意思应该是用bitmap,因为之前已经告诉了范围是1-n, 每一位bit代表一个数字,每出现一次就xor,  ...

感觉用bitmap就太trivial了,没有冒犯你的意思= =
回复 支持 反对

使用道具 举报

AIPointH 发表于 2016-3-5 18:35:30 | 显示全部楼层
这个就是用xor 认识一个学长面试刚遇到过 - -
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-5 19:40:35 | 显示全部楼层
AIPointH 发表于 2016-3-5 18:35
这个就是用xor 认识一个学长面试刚遇到过 - -

xor只能用在仅有一个数字duplicated的情况,或者我认为的xor方法不是你的方法?欢迎详聊~~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 20:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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