Y**G
发帖数: 1089 | 1 Given an array of integers, array value range from 0 to array.length -1, try
to find duplicate number in O(N) time.
如果没做过，要在面试30分钟写出来还是有难度地 |
p******n
发帖数: 9144 | 2 往hash table里面放呗； 发现放不进去就是有duplicte number啊； 两分钟就想出来了
try
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
Y**G
发帖数: 1089 | 3 打回重写，不及格
来了
【在 p******n 的大作中提到】
: 往hash table里面放呗； 发现放不进去就是有duplicte number啊； 两分钟就想出来了
:
: try
|
Y**G
发帖数: 1089 | 4 另外要求:额外的内存使用是常熟。数组是可写的
来了
【在 p******n 的大作中提到】
: 往hash table里面放呗； 发现放不进去就是有duplicte number啊； 两分钟就想出来了
:
: try
|
M***r
发帖数: 79 | 5 Too easy. This line tells you everything "array value range from 0 to array.
length -1". Scan the array once and put the number into right position. |
x****o
发帖数: 29677 | 6
try
ARRAY有序没有?一个重复还是可能存在很多重复?额外内存只能用O(1)?
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
p******n
发帖数: 9144 | 7 我说的不对吗？就是个arraylist n啊，往里按数值放数据，满了就表示重复了
【在 Y**G 的大作中提到】
: 打回重写，不及格
:
: 来了
|
p******n
发帖数: 9144 | 8 数组是满的么？
【在 Y**G 的大作中提到】
: 另外要求:额外的内存使用是常熟。数组是可写的
:
: 来了
|
f*******n
发帖数: 12623 | 9 Hash table access is O(n) in worst case.
来了
【在 p******n 的大作中提到】
: 往hash table里面放呗； 发现放不进去就是有duplicte number啊； 两分钟就想出来了
:
: try
|
z*******3
发帖数: 13709 | 10 前面有人说了
就是做一个空的array
然后扫一遍，把每一个取到的值往空的里面放
偏移就是arrya上的integer
这个题其实类似用<<, >>, &, | 用一个整数来判断ascii code重复的情况
try
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
|
|
M***r
发帖数: 79 | 11 LZ mentioned the given array can be overwritten, so a new array is
unnecessary. just swap values. when two swapping values equal, you find the
dup.
【在 z*******3 的大作中提到】
: 前面有人说了
: 就是做一个空的array
: 然后扫一遍，把每一个取到的值往空的里面放
: 偏移就是arrya上的integer
: 这个题其实类似用<<, >>, &, | 用一个整数来判断ascii code重复的情况
:
: try
|
z*******3
发帖数: 13709 | 12 这个要是我就先不说
估计对方会问有没有更好的方法
然后想一下再告诉对方
the
【在 M***r 的大作中提到】
: LZ mentioned the given array can be overwritten, so a new array is
: unnecessary. just swap values. when two swapping values equal, you find the
: dup.
|
g**e
发帖数: 6127 | 13 这种问烂了的题没做过只能说是没好好准备面试
try
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
p******n
发帖数: 9144 | 14 ft，那我就对了啊
【在 f*******n 的大作中提到】
: Hash table access is O(n) in worst case.
:
: 来了
|
p******n
发帖数: 9144 | 15 所以我问数组是不是满的，如果不满，就没法swap了
the
【在 M***r 的大作中提到】
: LZ mentioned the given array can be overwritten, so a new array is
: unnecessary. just swap values. when two swapping values equal, you find the
: dup.
|
z*******3
发帖数: 13709 | 16 错了，老大，对比hashtable里面的value时候要重新找一遍
这样就是O(n^2)了
【在 p******n 的大作中提到】
: ft，那我就对了啊
|
p******n
发帖数: 9144 | 17 ft，你为啥要找啊，往table里放是1，比较也是1，最多是2n，也即是O(n)，多明白啊
【在 z*******3 的大作中提到】
: 错了，老大，对比hashtable里面的value时候要重新找一遍
: 这样就是O(n^2)了
|
z*******3
发帖数: 13709 | 18 它说的是额外找一个来swap
也就是某人说的O(1)空间复杂度
【在 p******n 的大作中提到】
: 所以我问数组是不是满的，如果不满，就没法swap了
:
: the
|
z*******3
发帖数: 13709 | 19 您确定您明白什么是hashtable？
【在 p******n 的大作中提到】
: ft，你为啥要找啊，往table里放是1，比较也是1，最多是2n，也即是O(n)，多明白啊
|
W***o
发帖数: 6519 | 20 这方法不对，我这初学的都看出来了
【在 z*******3 的大作中提到】
: 前面有人说了
: 就是做一个空的array
: 然后扫一遍，把每一个取到的值往空的里面放
: 偏移就是arrya上的integer
: 这个题其实类似用<<, >>, &, | 用一个整数来判断ascii code重复的情况
:
: try
|
|
|
z*******3
发帖数: 13709 | 21 我跟这个id说的是一个方法
发信人: Mixer (Mixer), 信区: Java
标 题: Re: 今天碰到一个面试题
发信站: BBS 未名空间站 (Wed May 22 16:41:54 2013, 美东)
Too easy. This line tells you everything "array value range from 0 to array.
length -1". Scan the array once and put the number into right position.
【在 W***o 的大作中提到】
: 这方法不对，我这初学的都看出来了
|
p******n
发帖数: 9144 | 22 呵呵... 问题解决了不就完了；要不您给讲讲那儿不对？
【在 z*******3 的大作中提到】
: 您确定您明白什么是hashtable？
|
z*******3
发帖数: 13709 | 23 我已经告诉过你了
【在 p******n 的大作中提到】
: 呵呵... 问题解决了不就完了；要不您给讲讲那儿不对？
|
p******n
发帖数: 9144 | 24 你这个要用到O(n)的内存，错了
【在 z*******3 的大作中提到】
: 前面有人说了
: 就是做一个空的array
: 然后扫一遍，把每一个取到的值往空的里面放
: 偏移就是arrya上的integer
: 这个题其实类似用<<, >>, &, | 用一个整数来判断ascii code重复的情况
:
: try
|
p******n
发帖数: 9144 | 25 车轱辘话来回说，hash要是O(n^2),那还有人做hash么？
【在 z*******3 的大作中提到】
: 我已经告诉过你了
|
z*******3
发帖数: 13709 | 26 针对楼主的原文，楼主主贴倒是没有说要控制空间复杂度
对于空间复杂度是O(1)的方法，别人也说了，我表示同意
【在 p******n 的大作中提到】
: 你这个要用到O(n)的内存，错了
|
z*******3
发帖数: 13709 | 27 我放弃了，你赢了
【在 p******n 的大作中提到】
: 车轱辘话来回说，hash要是O(n^2),那还有人做hash么？
|
p******n
发帖数: 9144 | 28 hash 是O(1),n个数，就是O(n)，不过我这个也错了，因为也用了O(n)的内存
【在 z*******3 的大作中提到】
: 我已经告诉过你了
|
p******n
发帖数: 9144 | 29 真没意思 你赢了
【在 z*******3 的大作中提到】
: 我放弃了，你赢了
|
o***i
发帖数: 603 | 30 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 + ",");
}
}
System.out.println();
}
O(1)空间：
public void findDup(int[] numbers) {
int l = numbers.length;
for (int i = 0; i < l; i++) {
while (i != numbers[i]) {
if (numbers[i] == numbers[numbers[i]]) {
break;
} else {
int m = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = m;
}
}
}
//print results:
for (int i = 0; i < l; i++) {
if (i != numbers[i]) {
System.out.print(numbers[i] + ",");
}
}
System.out.println();
}
try
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
|
|
Y**G
发帖数: 1089 | 31 这是正解
【在 o***i 的大作中提到】
: 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]] ++;
: }
:
|
T*********g
发帖数: 496 | 32 .... pls consider bitset
try
【在 Y**G 的大作中提到】
: Given an array of integers, array value range from 0 to array.length -1, try
: to find duplicate number in O(N) time.
: 如果没做过，要在面试30分钟写出来还是有难度地
|
b*********a
发帖数: 723 | 33 package com.bruce.test;
public class TestApp {
public static void main(String[] args) {
int[] arr = { 2, 1, 3, 4, 11, 2, 6, 1, 12, 4, 11, 2, 12, 11, 11 };
System.out.println("O(n) space");
OnFindDuplicate(arr);
System.out
.println("\nO(1) space, but duplicated output sometimes like
11");
OoneFindDuplicate(arr);
System.out.println("\nO(1) space, no duplicated output ");
OoneFindDuplicate2(arr);
}
// need a new array as a counter
public static void OnFindDuplicate(int[] arr) {
int[] counter = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
counter[arr[i]]++;
if (counter[arr[i]] == 2) {
System.out.print(arr[i] + ",");
}
}
}
// when you are trying to exchange a number to the right place and find
// already one there, the number is duplicate
public static void OoneFindDuplicate(int[] arr) {
int temp = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i && arr[arr[i]] != arr[i]) {
temp = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = temp;
} else if (arr[i] != i && arr[arr[i]] == arr[i]) {
System.out.print(arr[i] + ",");
}
}
}
// input array itself can be used as a counter
public static void OoneFindDuplicate2(int[] arr) {
int temp = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == i) {
arr[i] = -1;
} else if (arr[i] >= 0 && arr[arr[i]] == arr[i]) {
System.out.print(arr[i] + ",");
arr[arr[i]] = -2;
} else if (arr[i] >= 0 && arr[arr[i]] >= 0) {
temp = arr[arr[i]];
arr[arr[i]] = -1;
arr[i] = temp;
} else if (arr[i] >= 0 && arr[arr[i]] < 0) {
if (arr[arr[i]] == -1)
System.out.print(arr[i] + ",");
arr[arr[i]] = arr[arr[i]] - 1;
}
}
}
} |
s***o
发帖数: 2191 | 34 while inside for，第一感觉不是o(n)
【在 Y**G 的大作中提到】
: 这是正解
:
:
|
k****i
发帖数: 101 | 35
public static int solveDuplicateElement(Integer[] ar) {
int pos = 0, len = ar.length, bigO = 0;
while (pos < len) {
int slot = ar[pos];
if (slot == pos || slot == len) {
// being in place or invalidated
++pos;
} else {
int next = ar[slot];
if (next == slot) {
// to invalidate duplicate
ar[pos] = len;
++pos;
} else {
// to reshuffle postion
int temp = slot;
ar[pos] = next;
ar[slot] = temp;
}
}
++bigO;
}
return bigO;
}
@Test
public void testSolveDuplicateElement() {
int len = 1000;
Integer[] ar = new Integer[len];
Random rand = new Random();
for (int i = 0; i < len; i++) {
ar[i] = rand.nextInt(len);
}
List before = new ArrayList(
new HashSet(Arrays.asList(ar)));
Collections.sort(before);
int bigO = solveDuplicateElement(ar);
List after = new ArrayList();
for (int el : ar) {
if (el != len) {
after.add(el);
}
}
Collections.sort(after);
assertEquals(before, after);
assertTrue(bigO < len * 2);
}
【在 Y**G 的大作中提到】
: 另外要求:额外的内存使用是常熟。数组是可写的
:
: 来了
|
B********r
发帖数: 397 | 36 Super easy, in ruby:
arr.select{|e| arr.count(e) > 1}.uniq
Or a more verbose version:
arr.each_with_index do |e, i|
t = arr[e-1]
arr[e-1] = e
arr[i] = t
end |
