m****r 发帖数: 141 | 1 Design a method findEvenFreq(int[] a), which returns the single integer
value in the array which occurs with even frequency. Other numbers occur odd
numbers , which may be 7, 11 or even larger. All integers will be positive.
What if the integers are continuous.
For example, [1, 2, 3, 1] should return 1.
What if the integers may not be continuous.
example, [4, 8, 7, 5, 8 ] should return 8
The largest number can be INT_MAX.
I know how to solve it by hahstable.
Better ideas about O(1) space with O(n) time ?
thanks |
l*****a 发帖数: 14598 | 2 I assume that you can only use a counter like
bool counter[65535];
int counter[65535]
odd
positive.
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Design a method findEvenFreq(int[] a), which returns the single integer : value in the array which occurs with even frequency. Other numbers occur odd : numbers , which may be 7, 11 or even larger. All integers will be positive. : What if the integers are continuous. : For example, [1, 2, 3, 1] should return 1. : What if the integers may not be continuous. : example, [4, 8, 7, 5, 8 ] should return 8 : The largest number can be INT_MAX. : I know how to solve it by hahstable. : Better ideas about O(1) space with O(n) time ?
|
p*****2 发帖数: 21240 | 3 他要求O(1)space
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I assume that you can only use a counter like : bool counter[65535]; : int counter[65535] : : odd : positive.
|
l*****a 发帖数: 14598 | 4 我认为
固定space就是O(1)
所谓O(n)的意思是随着输入的增长,所需空间线性增长
。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他要求O(1)space
|
p*****2 发帖数: 21240 | 5
有道理。不过这个跟hashtable不一样吗?hashtable说不定比这个还省空间。而且如果
变成int64的话,空间不就增加了?
我怎么感觉应该用异或呢?不过我没导出来公式呢。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我认为 : 固定space就是O(1) : 所谓O(n)的意思是随着输入的增长,所需空间线性增长 : 。。。
|
l*****a 发帖数: 14598 | 6 你说得对
但是只能这么做了。否则咋办
不知道LZ在那里看到的题。。。
异或感觉上肯定不成
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 有道理。不过这个跟hashtable不一样吗?hashtable说不定比这个还省空间。而且如果 : 变成int64的话,空间不就增加了? : 我怎么感觉应该用异或呢?不过我没导出来公式呢。
|
q********c 发帖数: 1774 | 7 O(1) space means no extra space.Maybe we can use partition to solve this,
though don't have a solid idea now. |
B******5 发帖数: 4676 | 8 这个要是design成bit operation会更合理吧
话说没出现过的数难道不也是偶数次?或许我强词夺理了。。。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I assume that you can only use a counter like : bool counter[65535]; : int counter[65535] : : odd : positive.
|
j*****j 发帖数: 201 | 9 异或好像是只有一两个出现一次,其余都出现两次的情况
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 有道理。不过这个跟hashtable不一样吗?hashtable说不定比这个还省空间。而且如果 : 变成int64的话,空间不就增加了? : 我怎么感觉应该用异或呢?不过我没导出来公式呢。
|
p*****2 发帖数: 21240 | 10
这个题不就是只有一个出现偶次数吗?
【在 j*****j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 异或好像是只有一两个出现一次,其余都出现两次的情况
|
|
|
l*****a 发帖数: 14598 | 11 那么多不一样的你怎么把它们消掉?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个题不就是只有一个出现偶次数吗?
|
p*****2 发帖数: 21240 | 12
看错了。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那么多不一样的你怎么把它们消掉?
|
e****r 发帖数: 581 | 13 continuous & 数都只出现一次,even的出现两次
int findEvenFreq(vector& arr) {
int i = 0;
const int n = arr.size();
while (i < n) {
if (arr[i] < 0) {
i++; continue;
}
int j = arr[i] % n;
if (arr[i] + arr[j] == -1) return arr[i];
if (j > i) {
int t = arr[j];
arr[j] = -arr[i]-1;
arr[i] = t;
} else i++;
}
return -1;
}
odd
positive.
【在 m****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Design a method findEvenFreq(int[] a), which returns the single integer : value in the array which occurs with even frequency. Other numbers occur odd : numbers , which may be 7, 11 or even larger. All integers will be positive. : What if the integers are continuous. : For example, [1, 2, 3, 1] should return 1. : What if the integers may not be continuous. : example, [4, 8, 7, 5, 8 ] should return 8 : The largest number can be INT_MAX. : I know how to solve it by hahstable. : Better ideas about O(1) space with O(n) time ?
|
p*****2 发帖数: 21240 | 14 不都是正数吗?
【在 e****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : continuous & 数都只出现一次,even的出现两次 : int findEvenFreq(vector& arr) { : int i = 0; : const int n = arr.size(); : while (i < n) { : if (arr[i] < 0) { : i++; continue; : } : int j = arr[i] % n; : if (arr[i] + arr[j] == -1) return arr[i];
|
e****r 发帖数: 581 | 15 类似的方法可以做类似 1 1 1 2 2 这种很多数字出现频率可能高于1
就是对于数a[i],得把它放到j=a[i]%n的位置(n是数组长度)
如果:
(0) 如果a[i]已经在正确的位置(i==j)或者a[i]<0,直接i++
(1) a[j] == a[i],那么把a[j]变成-a[i]-1, i++
(2) a[j] == -a[i]-1,那么把a[j]变成a[i], i++
(3) otherwise,交换a[i]和a[j],i不变
空间O(1),时间O(n)
最后再O(n)找那个负数,假设是a[k]。返回-a[k]+1就行
【在 e****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : continuous & 数都只出现一次,even的出现两次 : int findEvenFreq(vector& arr) { : int i = 0; : const int n = arr.size(); : while (i < n) { : if (arr[i] < 0) { : i++; continue; : } : int j = arr[i] % n; : if (arr[i] + arr[j] == -1) return arr[i];
|
e****r 发帖数: 581 | 16 看15楼我的说明。那个code是只针对连续、每个数出现一次、一个数出现两次的
15楼我的说明是针对连续的情况,不限出现多少次
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不都是正数吗?
|
p*****2 发帖数: 21240 | 17
(3)会不会死循环呢?
【在 e****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 类似的方法可以做类似 1 1 1 2 2 这种很多数字出现频率可能高于1 : 就是对于数a[i],得把它放到j=a[i]%n的位置(n是数组长度) : 如果: : (0) 如果a[i]已经在正确的位置(i==j)或者a[i]<0,直接i++ : (1) a[j] == a[i],那么把a[j]变成-a[i]-1, i++ : (2) a[j] == -a[i]-1,那么把a[j]变成a[i], i++ : (3) otherwise,交换a[i]和a[j],i不变 : 空间O(1),时间O(n) : 最后再O(n)找那个负数,假设是a[k]。返回-a[k]+1就行
|
e****r 发帖数: 581 | 18 如果不连续,我的想法还是用类似的方法(其实就是hash)
稍微麻烦一些。相同的数hash(%)到一起,用一样的方法处理
不同的数hash到一起,得用open addressing
(0) 如果a[i]已经在正确的位置(i==j)或者a[i]<0,直接i++
(1) a[j] == a[i], a[j] <- -a[i]-1, i++
(2) a[j] == -a[i]-1, a[j] <- a[i], i++
(3) otherwise, 如果((a[j] > 0) && (a[j] % n == j)) || ((a[j] < 0) && ((-a[j]
+1) % n == j))就说明是collision了(我们估且认为不同的数hash到一起才是
collision)。没有collision的话,就直接交换a[i]和a[j],i不变
处理collision就用open addressing:一个一个搜索,知道找到一个尚未处理过的位置
,或者找到正确的hash slot
细节蛮多的,基本上就是实现open addressing了……
大概意思就是这样
【在 e****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 类似的方法可以做类似 1 1 1 2 2 这种很多数字出现频率可能高于1 : 就是对于数a[i],得把它放到j=a[i]%n的位置(n是数组长度) : 如果: : (0) 如果a[i]已经在正确的位置(i==j)或者a[i]<0,直接i++ : (1) a[j] == a[i],那么把a[j]变成-a[i]-1, i++ : (2) a[j] == -a[i]-1,那么把a[j]变成a[i], i++ : (3) otherwise,交换a[i]和a[j],i不变 : 空间O(1),时间O(n) : 最后再O(n)找那个负数,假设是a[k]。返回-a[k]+1就行
|
e****r 发帖数: 581 | 19 不会,因为交换a[i]和a[j]后,原先的a[i]这个数在正确的位置(j),已经处理过了,
不会再处理这个数
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : (3)会不会死循环呢?
|
e****r 发帖数: 581 | 20 刚漏了一点,改了
每次循环,如果a[i]已经在正确的位置,就直接i++什么都不用做
判断a[i]是否在正确的位置的依据是:
(j == i) || (a[i] < 0)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : (3)会不会死循环呢?
|