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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 他要求O(1)space
|
p*****2
发帖数: 21240 | 5
有道理。不过这个跟hashtable不一样吗？hashtable说不定比这个还省空间。而且如果
变成int64的话，空间不就增加了？
我怎么感觉应该用异或呢？不过我没导出来公式呢。
【在 l*****a 的大作中提到】
: 我认为
: 固定space就是O(1)
: 所谓O(n)的意思是随着输入的增长，所需空间线性增长
: 。。。
|
l*****a
发帖数: 14598 | 6 你说得对
但是只能这么做了。否则咋办
不知道LZ在那里看到的题。。。
异或感觉上肯定不成
【在 p*****2 的大作中提到】
:
: 有道理。不过这个跟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 的大作中提到】
: I assume that you can only use a counter like
: bool counter[65535];
: int counter[65535]
:
: odd
: positive.
|
j*****j
发帖数: 201 | 9 异或好像是只有一两个出现一次，其余都出现两次的情况
【在 p*****2 的大作中提到】
:
: 有道理。不过这个跟hashtable不一样吗？hashtable说不定比这个还省空间。而且如果
: 变成int64的话，空间不就增加了？
: 我怎么感觉应该用异或呢？不过我没导出来公式呢。
|
p*****2
发帖数: 21240 | 10
这个题不就是只有一个出现偶次数吗？
【在 j*****j 的大作中提到】
: 异或好像是只有一两个出现一次，其余都出现两次的情况
|
|
|
l*****a
发帖数: 14598 | 11 那么多不一样的你怎么把它们消掉？
【在 p*****2 的大作中提到】
:
: 这个题不就是只有一个出现偶次数吗？
|
p*****2
发帖数: 21240 | 12
看错了。
【在 l*****a 的大作中提到】
: 那么多不一样的你怎么把它们消掉？
|
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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 不都是正数吗？
|
p*****2
发帖数: 21240 | 17
(3)会不会死循环呢？
【在 e****r 的大作中提到】
: 类似的方法可以做类似 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 的大作中提到】
: 类似的方法可以做类似 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 的大作中提到】
:
: (3)会不会死循环呢？
|
e****r
发帖数: 581 | 20 刚漏了一点，改了
每次循环，如果a[i]已经在正确的位置，就直接i++什么都不用做
判断a[i]是否在正确的位置的依据是：
(j == i) || (a[i] < 0)
【在 p*****2 的大作中提到】
:
: (3)会不会死循环呢？
|
