j**l
发帖数: 2911 | 1 这里数组是有序的，也就是重复的元素一定是连续排列的。实际上hash table可以O(n)
时间完成，而且可以对付非有序数组的情形，但是好像很难用到有序这个条件。这里规
定不用hash table。
规定用原数组空间存储删除重复元素后shrink的数组。平凡解法大家应该都能想到。设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度也是O(n)。
还有没有更好的方法？想了一下，假如重复元素的那段数比较长，上面方法的线性跳过
可能比较慢。是否可以用改进的binary search(如果有多个元素满足查找要求，返回下
标最大的那个），返回重复元素的最后一个位置，这样就可以log(n)时间跳过那段重复
元素了。
但不清楚这种方法复杂度是多少。假设有k个不同元素，复杂度是k*log(n)么? 是否在
最坏情况下退化为n*log(n)？
还有更好的方法么(不用hash table, 不用新的存储空间)？ |
j**l
发帖数: 2911 | 2 或者有没可能借用Brent找环算法的思想，设置一个步长s, 每次步长加倍的找最后一个
重复元素的位置？ |
h**6
发帖数: 4160 | 3 我觉得楼上的想法很好，每找到一个新元素，假设在位置n，那么先检查n+1，相同则检
查n+2，然后n+4, n+8, n+16依次翻倍。如果在n+2^m处相同而n+2^(m+1)处不同，则在n
+2^m和n+2^(m+1)之间使用二分法查找新元素的出现位置。 |
j**l
发帖数: 2911 | 4 个人觉得,在面试中遇到,可先提出用Hash,随即指出这种方法需要额外空间，虽然也可以
处理非排序数组(优点)，但对于本题，并没有很好的利用到排序这个已知条件。
然后给出平凡解法，白板coding。
然后抢在面试官问你还有什么改进之前，主动提出对平凡解法的各种加速策略。
最后想一下好的test cases, 尽可能考虑各种情形。
还可以展开来和面试官谈谈Hash table, binary search, 改进的binary search,
以及其它相应的话题，应该能达到让他满意的效果了吧。 |
r****o
发帖数: 1950 | 5 恩，不错。
【在 j**l 的大作中提到】
: 个人觉得,在面试中遇到,可先提出用Hash,随即指出这种方法需要额外空间，虽然也可以
: 处理非排序数组(优点)，但对于本题，并没有很好的利用到排序这个已知条件。
: 然后给出平凡解法，白板coding。
: 然后抢在面试官问你还有什么改进之前，主动提出对平凡解法的各种加速策略。
: 最后想一下好的test cases, 尽可能考虑各种情形。
: 还可以展开来和面试官谈谈Hash table, binary search, 改进的binary search,
: 以及其它相应的话题，应该能达到让他满意的效果了吧。
|
a*******h
发帖数: 123 | 6 你的O(n)的算法其实用到了排好序的条件，当 i 找到不同上一次写入的元素的时候，根
据有序立马可以判断出这是一个没出现过的元素。
n)
设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
也是O(n)。
【在 j**l 的大作中提到】
: 这里数组是有序的，也就是重复的元素一定是连续排列的。实际上hash table可以O(n)
: 时间完成，而且可以对付非有序数组的情形，但是好像很难用到有序这个条件。这里规
: 定不用hash table。
: 规定用原数组空间存储删除重复元素后shrink的数组。平凡解法大家应该都能想到。设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度也是O(n)。
: 还有没有更好的方法？想了一下，假如重复元素的那段数比较长，上面方法的线性跳过
: 可能比较慢。是否可以用改进的binary search(如果有多个元素满足查找要求，返回下
: 标最大的那个），返回重复元素的最后一个位置，这样就可以log(n)时间跳过那段重复
: 元素了。
: 但不清楚这种方法复杂度是多少。假设有k个不同元素，复杂度是k*log(n)么? 是否在
: 最坏情况下退化为n*log(n)？
|
j**l
发帖数: 2911 | 7 平凡解法是用到排好序的条件的，只需要和最后一个写入元素比较
Hash解法都是O(1)时间找到，没有用到排序。
，根
【在 a*******h 的大作中提到】
: 你的O(n)的算法其实用到了排好序的条件，当 i 找到不同上一次写入的元素的时候，根
: 据有序立马可以判断出这是一个没出现过的元素。
:
: n)
: 设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
: 过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
: 也是O(n)。
|
a*******h
发帖数: 123 | 8 呵呵，我没看仔细。
【在 j**l 的大作中提到】
: 平凡解法是用到排好序的条件的，只需要和最后一个写入元素比较
: Hash解法都是O(1)时间找到，没有用到排序。
:
: ，根
|
y**i
发帖数: 1112 | 9 问个基本问题啊，如果用hash的话，空间需求是多少啊？
n)
设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
也是O(n)。
【在 j**l 的大作中提到】
: 这里数组是有序的，也就是重复的元素一定是连续排列的。实际上hash table可以O(n)
: 时间完成，而且可以对付非有序数组的情形，但是好像很难用到有序这个条件。这里规
: 定不用hash table。
: 规定用原数组空间存储删除重复元素后shrink的数组。平凡解法大家应该都能想到。设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度也是O(n)。
: 还有没有更好的方法？想了一下，假如重复元素的那段数比较长，上面方法的线性跳过
: 可能比较慢。是否可以用改进的binary search(如果有多个元素满足查找要求，返回下
: 标最大的那个），返回重复元素的最后一个位置，这样就可以log(n)时间跳过那段重复
: 元素了。
: 但不清楚这种方法复杂度是多少。假设有k个不同元素，复杂度是k*log(n)么? 是否在
: 最坏情况下退化为n*log(n)？
|
j**l
发帖数: 2911 | 10 最多O(n), 如果不重复的元素个数是k的话，O(k)
【在 y**i 的大作中提到】
: 问个基本问题啊，如果用hash的话，空间需求是多少啊？
:
: n)
: 设置两个读写指针(下标)i, j。其中i用于扫描整个数组，j用于写新数组的元素。扫描
: 过程中，如果A[i] == A[j]则跳过，直到找到不同的元素，然后写入并更新j。复杂度
: 也是O(n)。
|
|
|
w******1
发帖数: 520 | 11 假设用的是HASH, HASH 的KEY 的值是多少， VALUE 对应的值是多少呢？ |
j**l
发帖数: 2911 | 12 Key就是每个数组元素，value你可以累加该元素出现的总次数，也完全可以不去管它。
因为这里只关心新来的每一个元素是否已经在Hash表中存在，存在就表明重复，并不关心它重复出现了多少次。
【在 w******1 的大作中提到】
: 假设用的是HASH, HASH 的KEY 的值是多少， VALUE 对应的值是多少呢？
|
y**i
发帖数: 1112 | 13 这里我一直都不太懂，能指教一下吗？
如果key是每个数组的元素，假如说，数组的取值范围是从1-1000，数组大小是100，那
不是需要1000个hash的空间去存储？当然实际有值的空间<=100。如果要压缩空间，如
何压缩能解决碰撞问题？
关心它重复出现了多少次。
【在 j**l 的大作中提到】
: Key就是每个数组元素，value你可以累加该元素出现的总次数，也完全可以不去管它。
: 因为这里只关心新来的每一个元素是否已经在Hash表中存在，存在就表明重复，并不关心它重复出现了多少次。
|
j**l
发帖数: 2911 | 14 是这样的，Hash表初始为空，如果新来一个元素，如果不在表内才动态插入。如果已经
在表内的就不做任何操作。
你可以参考一下STL的vector,可以为空，可以先预留一定空间，可以动态增长。当然在
内部存储空间不足时候需要重新分配并扩大可用存储空间，需要一些额外开销。
比如数组为 1 1 2 2 2 3 4 4 5, 大小为9
Hash表只需要存1, 2, 3, 4, 5，大小为5
【在 y**i 的大作中提到】
: 这里我一直都不太懂，能指教一下吗？
: 如果key是每个数组的元素，假如说，数组的取值范围是从1-1000，数组大小是100，那
: 不是需要1000个hash的空间去存储？当然实际有值的空间<=100。如果要压缩空间，如
: 何压缩能解决碰撞问题？
:
: 关心它重复出现了多少次。
|
j**l
发帖数: 2911 | 15 你的思路其实说到一种情况，就是已知取值的范围。这种情形也可以用数组（桶）来代
替Hash表的，每个Key直接作为下标去查找。比如对于ASCII字符，你用一个256大小的
数组就可以了。如果数值范围小，这种方法比Hash表还要快。但是这种方法可能会浪费
一些空间，而Hash表的好处就是只存储实际用到的元素。在PIE(Programming
Interview Exposed)一书中介绍Hash表的时候比较过了这两种方法。
【在 y**i 的大作中提到】
: 这里我一直都不太懂，能指教一下吗？
: 如果key是每个数组的元素，假如说，数组的取值范围是从1-1000，数组大小是100，那
: 不是需要1000个hash的空间去存储？当然实际有值的空间<=100。如果要压缩空间，如
: 何压缩能解决碰撞问题？
:
: 关心它重复出现了多少次。
|
j**l
发帖数: 2911 | 16 这里暂不考虑Hash表的碰撞问题。假定Hash函数设计的比较好，碰撞很少发生。
【在 y**i 的大作中提到】
: 这里我一直都不太懂，能指教一下吗？
: 如果key是每个数组的元素，假如说，数组的取值范围是从1-1000，数组大小是100，那
: 不是需要1000个hash的空间去存储？当然实际有值的空间<=100。如果要压缩空间，如
: 何压缩能解决碰撞问题？
:
: 关心它重复出现了多少次。
|
y**i
发帖数: 1112 | 17 你举的例子是数组元素个数大于数组取值范围的情况，就比如说如果数组的最后一个值
不是5而是1000，那hash表也只需要存1，2，3，4，1000吗？那这样的话，要么1000是
存在数组下标为1000的地方，要么紧接着4的后面存，如果是后者，那下次再遇到1000
的时候怎么定位呢？如果从头再查找一边的话，那就不是O(1)的查找时间了吧？我就是
这里不太明白。如果是前者，我知道的是可以取余数（或者乘法等）来定位，比如所有
数都余100，那么1000实际上是存在数组下标10的位置，这样就需要拉链法来解决碰撞
问题了。动态增长空间我大概明白的，大概就是每次的size不够了的话动态分配两倍
size的空间。
【在 j**l 的大作中提到】
: 是这样的，Hash表初始为空，如果新来一个元素，如果不在表内才动态插入。如果已经
: 在表内的就不做任何操作。
: 你可以参考一下STL的vector,可以为空，可以先预留一定空间，可以动态增长。当然在
: 内部存储空间不足时候需要重新分配并扩大可用存储空间，需要一些额外开销。
: 比如数组为 1 1 2 2 2 3 4 4 5, 大小为9
: Hash表只需要存1, 2, 3, 4, 5，大小为5
|
j**l
发帖数: 2911 | 18 这里不讨论Hash表内部具体的实现细节，假定Hash都是O(1)时间查找到。实际运行时候
是很有可能遇到你说的问题的.槽位不够肯定要有冲突,拉链法是其中一种解决方法.
除非面试官问到Hash表的具体细节，你才跟他讨论hash函数，解决冲突，拉链法，装填
因子，再hash, 二次hash这些技术。
1000
【在 y**i 的大作中提到】
: 你举的例子是数组元素个数大于数组取值范围的情况，就比如说如果数组的最后一个值
: 不是5而是1000，那hash表也只需要存1，2，3，4，1000吗？那这样的话，要么1000是
: 存在数组下标为1000的地方，要么紧接着4的后面存，如果是后者，那下次再遇到1000
: 的时候怎么定位呢？如果从头再查找一边的话，那就不是O(1)的查找时间了吧？我就是
: 这里不太明白。如果是前者，我知道的是可以取余数（或者乘法等）来定位，比如所有
: 数都余100，那么1000实际上是存在数组下标10的位置，这样就需要拉链法来解决碰撞
: 问题了。动态增长空间我大概明白的，大概就是每次的size不够了的话动态分配两倍
: size的空间。
|
k*******d
发帖数: 701 | 19 1.取有序数组最大的那个作为size
2.n=size/8(假设一个int 8 位)个int数，值为0
3.然后遍历有序数组，根据有序数组元素的值k(假设为k)将相应n个int数的第k位值为1
,如果遇到重复数则跳过 |
s******9
发帖数: 84 | 20 bitmap
为1
【在 k*******d 的大作中提到】
: 1.取有序数组最大的那个作为size
: 2.n=size/8(假设一个int 8 位)个int数，值为0
: 3.然后遍历有序数组，根据有序数组元素的值k(假设为k)将相应n个int数的第k位值为1
: ,如果遇到重复数则跳过
|
|
|
s******9
发帖数: 84 | 21 bitmap
为1
【在 k*******d 的大作中提到】
: 1.取有序数组最大的那个作为size
: 2.n=size/8(假设一个int 8 位)个int数，值为0
: 3.然后遍历有序数组，根据有序数组元素的值k(假设为k)将相应n个int数的第k位值为1
: ,如果遇到重复数则跳过
|
w******1
发帖数: 520 | |
w******1
发帖数: 520 | 23 1. HASH, 不允许
2. SORTING, COMPARE ONE BY ONE.
3........ |
w****l
发帖数: 88 | 24 放到set中，遍历set,自动去重，无须任何额外空间，可否？
假设 set=｛1，1，2，2，3，3，3，4，4，5，5，6｝
返回｛1，2，3，4，5，6｝。不知道是否符合要求 |
c*****u
发帖数: 562 | 25
不须额外空间？Set放哪儿？
【在 w****l 的大作中提到】
: 放到set中，遍历set,自动去重，无须任何额外空间，可否？
: 假设 set=｛1，1，2，2，3，3，3，4，4，5，5，6｝
: 返回｛1，2，3，4，5，6｝。不知道是否符合要求
|
c*****o
发帖数: 178 | 26 O(n) and no extra space.
int delete_dup(int* input, int length_d){
if(length_d <= 1 || !input)
return -1;
int pilot_d = 0;
int pilot_u = 0;
while(pilot_d < length_d){
do{
input[pilot_u++] = input[pilot_d++];
}while(input[pilot_d] != input[pilot_d+1] && pilot_d < length_d);
do{
pilot_d++;
}while(input[pilot_d] == input[pilot_d+1] && pilot_d < length_d);
}
return pilot_u;
} |
