c******t
发帖数: 391 | 1 How about this one? Is this O(NlogN) solution?
#include
#include
using namespace std;
void finddup(int arr[], int length){
hash_map hm;
cout<
for(int i=0; i
hm[arr[i]]++;
}
hash_map::iterator it;
int dup=0;
for(int i=0; i
it=hm.find(arr[i]);
if(it->second>1){
dup=it->first;
cout<
}
}
cout<
}
void main(){... 阅读全帖 |
|
c********r
发帖数: 286 | 2 public class FindDuplicatedInt {
public static int FindDup(int[] arr)
{
if(arr.length > 1002 || arr == null) return -1;
int checker = 0;
for(int i = 0;i
int val = arr[i];
if((checker & (1<0){
return val;
}
checker |= (1<
}
return -1;
}
public static void main(String[] args) {
int [] a = new int[]{1,2,3,4,5,6,7,8,9,10,2};
System.out.pri... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3
我写了一个练练。
def findDup(l):
xor=0
for i in l:
xor^=i
checker=1
while not (xor & checker):
checker<<=1
ans=[0,0]
for i in l:
if i&checker:
ans[0]^=i
else:
ans[1]^=i
return ans
l=[1,1,2,2,3,3,4,5]
print findDup(l) |
|
s*******n
发帖数: 305 | 4
这个没有问题吗？用上面的code跑了一下， 会出问题呀， 还是我的理解有问题。
findDup({0,1,2,2,3}）=6;
findDup({0,1,2,3,3}) =7;
e.g.:
For {0,1,2,3,3}, when i =4:
ans = ans^A[4] = ans^3= 0^3=3;
ans = ans^i =3^4=7; |
|
s*******n
发帖数: 305 | 5
....., 又试了这个解法，把long改成int了，可是结果也不一样了。
findDup({0,1,2,2,3}）=-2;
findDup({0,1,2,3,3}) =-1;
e.g.:
For {0,1,2,3,3},
i=0, ret=0-0=0;
i=1, ret=1-1=0;
i=2, ret=2-2=0;
i=3, ret=3-3=0;
i=4, ret=3-4=-1;
是不是我理解力真有问题了，今天不适合做题了。。。 |
|
s*******r
发帖数: 2697 | 6 O(n)
int findDup(int []a,int n){
long ret=0;
for(int i=0;i
ret+=a[i]-i;
}
return ret;
} |
|
f*******t
发帖数: 7549 | 7 最优解：
int findDup(int[] A) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= i;
}
return ans;
} |
|
c*******r
发帖数: 309 | 8 O(n). 一个小bug, i<=n
int findDup(int []a,int n){
long ret=0;
for(int i=0;i
ret+=a[i]-i;
}
return ret;
} |
|
b***i
发帖数: 3043 | 9
最优解：
int findDup(int[] A, int n) {
int ans = n; |
|
u*****o
发帖数: 1224 | 10 这题数不能从0开始啊，必须是从1开始，才能保证和下标一个个消掉。
原题是数组只有1-10000，然后size是10001
你的例子的话呢，就是
findDup({1,2,2,3,4})
要用0进数组的话得改一下下标。 |
|
p****e
发帖数: 183 | 11 应该这样吧
// A[] has (n+1) elements, range: (1...n), only one duplicate
int findDup(int A[], int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= (i+1);
}
ans ^= A[n];
return ans;
} |
|
L*******e
发帖数: 114 | 12 I wrote the following methods and ran some testings, it works OK. You need
go through the whole list. In your code, i < n, it never touches the last
element.
/**
* A[] has (n+1) elements, range: (1...n), only one duplicate
* @param a
* @return
*/
public static int findDup(int[] a){
int sum = 0;
for (int i = a.length - 1; i >= 0; i--){
sum += (a[i] - i);
}
return sum;
}
public static int findDup2(int[] a){
int sum = 0;
for (int i = 0; i < a.length; i++){
su... 阅读全帖 |
|
Q**F
发帖数: 995 | 13 你觉得这个可行吗？
class Solution
{
public:
int findDup(vector v)
{
int start =1; //搜索区间的下限
int end = v.size()-1; //搜素区间的上限
int count = 0; //搜索区间的个数
while(start < end)
{
for(int i=0; i
if(v[i] >=start && v[i] <= (start+end)/2)
{
count++;
}
}
if(count > ((start+end)/2 -start + 1))
{
end = (start+end)/2;
}
else
... 阅读全帖 |
|
o***i
发帖数: 603 | 14 O(N)空间：
public void findDup2(int[] numbers) {
int l = numbers.length;
int[] n2 = new int[l];
for (int i = 0; i < l; i++) {
n2[numbers[i]] ++;
}
//print results:
for (int i = 0; i < n2.length; i++) {
if (n2[i] > 1) {
System.out.print(i + ",");... 阅读全帖 |
|
