w****l
发帖数: 88 | 1 刚面完，感觉一般，估计挂了....
寒暄，文件里上的project,接下来算法：
find majority element in an array. 我说用hash table，但是空间效率
低，我自己说了个constant space的idea, 写code。 写完问我怎么extend
to最一般的情况, 我说了自己的idea, 然后说什么时间不够了，就不用写代码了，
他理解啥的..... |
b******v
发帖数: 1493 | 2 你的constant space的idea是什么呀
。
extend
写代码了，
.....
【在 w****l 的大作中提到】
: 刚面完，感觉一般，估计挂了....
: 寒暄，文件里上的project,接下来算法：
: find majority element in an array. 我说用hash table，但是空间效率
: 低，我自己说了个constant space的idea, 写code。 写完问我怎么extend
: to最一般的情况, 我说了自己的idea, 然后说什么时间不够了，就不用写代码了，
: 他理解啥的.....
|
f****4
发帖数: 1359 | |
w****l
发帖数: 88 | 4 就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
就记下来了。不是本人原始想法，本人是菜鸟级的).
【在 b******v 的大作中提到】
: 你的constant space的idea是什么呀
:
: 。
: extend
: 写代码了，
: .....
|
f****4
发帖数: 1359 | 5 可他只要知道那个数是majority啊，只要碰到相同ele vote++就好了啊
还有，啥叫最一般的情况啊？
谢谢
=
，觉得挺好，
【在 w****l 的大作中提到】
: 就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
: array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
: vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
: 就记下来了。不是本人原始想法，本人是菜鸟级的).
|
f******6
发帖数: 723 | 6 is this for summer intern or full-time position?
Good luck! |
w****l
发帖数: 88 | 7 majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
vote变
量。
【在 f****4 的大作中提到】
: 可他只要知道那个数是majority啊，只要碰到相同ele vote++就好了啊
: 还有，啥叫最一般的情况啊？
: 谢谢
:
: =
: ，觉得挺好，
|
w****l
发帖数: 88 | 8 New Graduate Full Time Position, Mountain View
【在 f******6 的大作中提到】
: is this for summer intern or full-time position?
: Good luck!
|
b******v
发帖数: 1493 | 9 这样的话，要扫描很多次吧？
=
，觉得挺好，
【在 w****l 的大作中提到】
: 就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
: array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
: vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
: 就记下来了。不是本人原始想法，本人是菜鸟级的).
|
w****l
发帖数: 88 | 10 一次就够了....
【在 b******v 的大作中提到】
: 这样的话，要扫描很多次吧？
:
: =
: ，觉得挺好，
|
|
|
b******v
发帖数: 1493 | 11 你第一次的扫描只是对array[0] vote吧
难道不要对array[1]...array[n-1]也做一次vote吗？
【在 w****l 的大作中提到】
: 一次就够了....
|
w****l
发帖数: 88 | 12 如果这么理解的话那就是多次扫描了，我个人认为constant time可以得到array[i]],
所以整个数
组就是依次扫描了，难道是多次扫描？ 不理解中....请指教....
【在 b******v 的大作中提到】
: 你第一次的扫描只是对array[0] vote吧
: 难道不要对array[1]...array[n-1]也做一次vote吗？
|
f****4
发帖数: 1359 | 13 哦，我把majority理解错了
可那样的话，还是只需要统计每个ele的出现次数啊，最后扫描出现次数大于n/2的就是
；这样的话对n/k的也能不做修改直接实现啊（只要比较出现次数大于n/k的就好了）
bless
【在 w****l 的大作中提到】
: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。
|
d*******8
发帖数: 785 | 14 不用的呀，当vote变零的时候 你也要更新Element然后重置vote为一
【在 b******v 的大作中提到】
: 你第一次的扫描只是对array[0] vote吧
: 难道不要对array[1]...array[n-1]也做一次vote吗？
|
c********t
发帖数: 1756 | 15 如果 ele > n/2 楼主的方法可行。如果是n/k, 搂主能不能讲讲两个votes 的方法。 |
l******4
发帖数: 207 | 16 co-ask
【在 c********t 的大作中提到】
: 如果 ele > n/2 楼主的方法可行。如果是n/k, 搂主能不能讲讲两个votes 的方法。
|
f****e
发帖数: 30 | 17 how to do that?
【在 w****l 的大作中提到】
: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。
|
a***9
发帖数: 364 | 18 lz的做法只用到constant space, 扫描一次就够了,
如果统计每个数出现的次数 就不是constant space了
【在 f****4 的大作中提到】
: 哦，我把majority理解错了
: 可那样的话，还是只需要统计每个ele的出现次数啊，最后扫描出现次数大于n/2的就是
: ；这样的话对n/k的也能不做修改直接实现啊（只要比较出现次数大于n/k的就好了）
: bless
|
a***9
发帖数: 364 | 19 make clear一件事，大于n/k的majority也是只有一个数么？并且所有的数都不超过n/k
吗？
【在 w****l 的大作中提到】
: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。
|
w****l
发帖数: 88 | 20 不是这个意思， 有可能有两个，比如k=3,那么就是要找出现频率 超过n/3的数， 至于
其他数是不是
也都小于这个数，不清楚....所以我一时没想出什么解法来...sigh.....估计是挂面了
....
/k
【在 a***9 的大作中提到】
: make clear一件事，大于n/k的majority也是只有一个数么？并且所有的数都不超过n/k
: 吗？
|
|
|
a***9
发帖数: 364 | 21 这个code测试了么 是到vote=0的时候往后就换成后面一个element吧
=
，觉得挺好，
【在 w****l 的大作中提到】
: 就是用一个vote变量，把这些数字想像成选举时候的candidate, 让一开始的element =
: array[0], 然后从数组第一个元素开始，如果等于element，vote++，如果不相等，
: vote--,当 vote 小于0的时候设为1 。(我以前复习的时候从一个人的博客里看来的，觉得挺好，
: 就记下来了。不是本人原始想法，本人是菜鸟级的).
|
a***9
发帖数: 364 | 22 2个变量怎么整？
如果 k = 4, 就有可能有3个大于n/4的元素吧
猜测可以用k-1个vote, 增vote时不用++，用vote+=k-1，减就用--，到0时换成后面的
元素
【在 w****l 的大作中提到】
: majority 定义是大于n/2的occurrence, 他问n/k怎么用vote的idea 做，我说用两个
: vote变
: 量。
|
w****l
发帖数: 88 | 23 测试过了，是正确的，至于扩展的版本，我还没有完全想明白......不好意思.....
【在 a***9 的大作中提到】
: 这个code测试了么 是到vote=0的时候往后就换成后面一个element吧
:
: =
: ，觉得挺好，
|
a***9
发帖数: 364 | 24 问一下element的元素不更新？那如果不是arr[0]怎么找的出来啊。。可能我理解错了
你意思
【在 w****l 的大作中提到】
: 测试过了，是正确的，至于扩展的版本，我还没有完全想明白......不好意思.....
|
w****l
发帖数: 88 | 25 我贴一下code 吧，基本版本，扩展的没想好：
#include
#include
int findMajorityElem(int array[], int n){
int maj_index =0;
int votes = 1;
for (int i = 1; i< n; i++){
if (array[i] == array[maj_index] ){
votes ++;
}else if(votes >0){
votes--;
}else{
maj_index = i;
votes = 1;
}
}
return array[maj_index];
}
//For testing purpose
int main(){
int arr[] ={1,3,3,3,1,2};
int nu |
a***9
发帖数: 364 | 26 对的吧。 你还是更新了的
【在 w****l 的大作中提到】
: 我贴一下code 吧，基本版本，扩展的没想好：
: #include
: #include
: int findMajorityElem(int array[], int n){
:
: int maj_index =0;
:
: int votes = 1;
:
: for (int i = 1; i< n; i++){
|
b*******y
发帖数: 239 | |
c********t
发帖数: 1756 | 28 大于n/k的element, 是不是得把数组无序变有序再找，preprocess: O(nlg(n)),
search time O(n) |
r**********1
发帖数: 292 | 29 对于[3,1,2,3]这个数组，你的findMajorityElem返回值是2，应该是3.
int findMajorityElem(int array[], int n){
int maj_index =0;
int votes = 1;
for (int i = 1; i< n; i++){
if (array[i] == array[maj_index] ){
votes ++;
}else if(votes >0){
votes--;
}else{
maj_index = i;
votes = 1;
}
}
return array[maj_index];
} |
b******v
发帖数: 1493 | 30 对，他那个算法有问题
【在 r**********1 的大作中提到】
: 对于[3,1,2,3]这个数组，你的findMajorityElem返回值是2，应该是3.
: int findMajorityElem(int array[], int n){
:
: int maj_index =0;
:
: int votes = 1;
:
: for (int i = 1; i< n; i++){
: if (array[i] == array[maj_index] ){
: votes ++;
|
|
|
f****4
发帖数: 1359 | 31 如果不是还有别的条件没讲清楚的话
这个votes的办法是求不出majority的
【在 r**********1 的大作中提到】
: 对于[3,1,2,3]这个数组，你的findMajorityElem返回值是2，应该是3.
: int findMajorityElem(int array[], int n){
:
: int maj_index =0;
:
: int votes = 1;
:
: for (int i = 1; i< n; i++){
: if (array[i] == array[maj_index] ){
: votes ++;
|
l******4
发帖数: 207 | 32 I have the similar solution.
There is k-1 votes.
each time check the k-1 votes. Here is the pseudocode.
for(i = 0 to n-1)
{
flag = true;
for (j = 0 to k-1)
{
if (a[i] == vote[j])
{
count[j]+=(k-1);
flag = false;
}
if ((a[i]!= vote[j]) &&(count[j] !=0)
{
count[j]--;
}
}
if (flag)
{
for (j = 0 to k-1)
{
if (count[j] == 0)
{
cou
【在 a***9 的大作中提到】
: 2个变量怎么整？
: 如果 k = 4, 就有可能有3个大于n/4的元素吧
: 猜测可以用k-1个vote, 增vote时不用++，用vote+=k-1，减就用--，到0时换成后面的
: 元素
|
w****l
发帖数: 88 | 33 条件是： more than n/2,不包括n/2，所以我认为那个算法还在这个条件下是work 的 |
b******v
发帖数: 1493 | 34 这样好像是可以的
【在 w****l 的大作中提到】
: 条件是： more than n/2,不包括n/2，所以我认为那个算法还在这个条件下是work 的
|
b******n
发帖数: 823 | 35 basic idea就是每次pair两个不同的element干掉，到最后剩下的就是majority；
同样的idea应该可以用到大于n/k的情况，每次pair k个不同element干掉，但是这个肯定达不到constant time |
h**6
发帖数: 4160 | 36 这个就是编程之美超级灌水王的问题。
在大小为n的数组里寻找(k-1)个超过(n/k)的数的复杂度为O(nk)，需要空间O(k) |
r**********1
发帖数: 292 | 37 是。条件也是n出现的次数是大于N/2（不包括这个，所以我的例子不对）
【在 h**6 的大作中提到】
: 这个就是编程之美超级灌水王的问题。
: 在大小为n的数组里寻找(k-1)个超过(n/k)的数的复杂度为O(nk)，需要空间O(k)
|
