k***g
发帖数: 166 | 1 这道题：
一个全是数字的array，只有一个出现的频率是偶数其他的都是奇数，把那个出线频率
是偶数的哥们找出来 |
w******e
发帖数: 1621 | |
y**********a
发帖数: 824 | 3 除非具体知道奇数的次数，否则没法常数空间。
空间时间 : O(n) O(n)
static List timeEfficient(int[]A) {
Map m=new HashMap<>();
for (int a:A)
if (!m.containsKey(a)) m.put(a, 1);
else m.put(a, m.get(a)+1);
List rel=new ArrayList<>();
for (Map.Entry e:m.entrySet())
if (e.getValue()%2==0)
{rel.add(e.getKey());break;}
return rel;
}
空间时间： O(1) O(nlogn)
static List spaceEconomical(int[]A) {
Arrays.sort(A);
Listrel=new ArrayList<>();
for (int s=0,e=s+1,n=A.length;s
while (e
if ((e-s)%2==0) {rel.add(A[s]);break;}
}
return rel;
} |
u*****o
发帖数: 1224 | 4 我记得这题用xor也可以做，好像是先找unique elements
比如说，1， 2， 2, 3
unique element是 1 2 3
然后xor这两个array, 1^2^2^3^1^2^3 = 2
就找出来2了
不过这个不比用hash table省空间呀 |
r*******k
发帖数: 1423 | 5 应该是时间空间都没省
时间还慢了点
有意思，算是一个思路，呵呵
【在 u*****o 的大作中提到】
: 我记得这题用xor也可以做，好像是先找unique elements
: 比如说，1， 2， 2, 3
: unique element是 1 2 3
: 然后xor这两个array, 1^2^2^3^1^2^3 = 2
: 就找出来2了
: 不过这个不比用hash table省空间呀
|
a******p
发帖数: 157 | 6 把所有数字都看成z零一串，按位运算，求和后mod2.
assume array of int.
bit i of the result = sum of bit i in all int %2==0?1:0
return result. |
Q*****a
发帖数: 33 | 7 考虑[1,3,3], [2,3,3]算法不成立
【在 a******p 的大作中提到】
: 把所有数字都看成z零一串，按位运算，求和后mod2.
: assume array of int.
: bit i of the result = sum of bit i in all int %2==0?1:0
: return result.
|
r***s
发帖数: 737 | 8 XOR
这个玩意非常恶心
【在 k***g 的大作中提到】
: 这道题：
: 一个全是数字的array，只有一个出现的频率是偶数其他的都是奇数，把那个出线频率
: 是偶数的哥们找出来
|
z*****u
发帖数: 3010 | |
l****i
发帖数: 2772 | 10 详细说说怎么xor？
【在 z*****u 的大作中提到】
: XOR
: 不看过答案 基本想不出来吧
|
|
|
w******e
发帖数: 1621 | 11 上面两楼能不能说说XOR具体的步骤，会不会是看错题了 |
l****i
发帖数: 2772 | 12 估计看错题了
【在 w******e 的大作中提到】
: 上面两楼能不能说说XOR具体的步骤，会不会是看错题了
|
j*d
发帖数: 96 | 13 这么多人都是在背leetcode答案。。。面试的时候直接露馅 |
l****i
发帖数: 2772 | |
D*********d
发帖数: 125 | 15 好吧没仔细看，看反了。
【在 l****i 的大作中提到】
: 不看题就写答案？
|
s*i
发帖数: 5025 | 16 到底有比这两个更牛的算法没有？
【在 y**********a 的大作中提到】
: 除非具体知道奇数的次数，否则没法常数空间。
: 空间时间 : O(n) O(n)
: static List timeEfficient(int[]A) {
: Map m=new HashMap<>();
: for (int a:A)
: if (!m.containsKey(a)) m.put(a, 1);
: else m.put(a, m.get(a)+1);
: List rel=new ArrayList<>();
: for (Map.Entry e:m.entrySet())
: if (e.getValue()%2==0)
|
