o****i
发帖数: 1706 | 1 A machine known as, equivalence tester, can determine whether two bank cards
correspond to the same
account by taking two cards at a time as input and outputting whether they
are equivalent. Give an
algorithm which invokes equivalence tester at most O(n lg n) to determine
whether there is a set of
more than n/2 equivalent cards in the given n bank cards. | k******4
发帖数: 94 | 2 每次取两张卡测试，如果返回true，随便留一张下来，否则都扔掉。
最后肯定就剩下两张或一张，两张测试是false的话，返回no。否则应该还需要再验证
下是否真的大约一半。
上面过程可以保证如果存在样的卡，肯定在留下的卡里面数量一直大于一半，
具体应该可以用数学归纳法证明。 | z***m
发帖数: 1602 | 3 1. 随便一张，可以把集合分成equivalent 和non-equivalent两类
2. 如果equivlent类里有多于n/2个， return true； 否则扔掉equivlent的所有卡，
回到1.
3. 如果卡都扔完了，还没有多于一半的那种卡，就return false | k******4
发帖数: 94 | 4 如过不幸每次equivalent里面都是空呢？时间复杂度是n^2？
【在 z***m 的大作中提到】
: 1. 随便一张，可以把集合分成equivalent 和non-equivalent两类
: 2. 如果equivlent类里有多于n/2个， return true； 否则扔掉equivlent的所有卡，
: 回到1.
: 3. 如果卡都扔完了，还没有多于一半的那种卡，就return false
| h*****u
发帖数: 1484 | 5 只剩一张如何判断呢？比如1,2,1,2,3和1,2,1,2,1
这题就是lc上的majority element吧，O(n)复杂度
存一个candidate和一个count
for (Card card : cards) {
if (count == 0) {
candidate = card;
count = 1;
} else if (testEquivalent(candidate, card)) {
count++;
} else {
count--;
}
}
return count > 0;
【在 k******4 的大作中提到】
: 每次取两张卡测试，如果返回true，随便留一张下来，否则都扔掉。
: 最后肯定就剩下两张或一张，两张测试是false的话，返回no。否则应该还需要再验证
: 下是否真的大约一半。
: 上面过程可以保证如果存在样的卡，肯定在留下的卡里面数量一直大于一半，
: 具体应该可以用数学归纳法证明。
| k******4
发帖数: 94 | 6 只有一张了，需要测试是否真的大约一半。
【在 h*****u 的大作中提到】
: 只剩一张如何判断呢？比如1,2,1,2,3和1,2,1,2,1
: 这题就是lc上的majority element吧，O(n)复杂度
: 存一个candidate和一个count
: for (Card card : cards) {
: if (count == 0) {
: candidate = card;
: count = 1;
: } else if (testEquivalent(candidate, card)) {
: count++;
: } else {
| o****i
发帖数: 1706 | 7 你这个目测不对，就走一遍的话，前面过去的卡就算扔掉了，后面的candidate不能和
前面的比较，而且这个题的意思，我的理解是如果set是(1,1,2,2,3)的话是可以过得，
你的算法貌似不能过这种情况，因为只有一个candidate。
【在 h*****u 的大作中提到】
: 只剩一张如何判断呢？比如1,2,1,2,3和1,2,1,2,1
: 这题就是lc上的majority element吧，O(n)复杂度
: 存一个candidate和一个count
: for (Card card : cards) {
: if (count == 0) {
: candidate = card;
: count = 1;
: } else if (testEquivalent(candidate, card)) {
: count++;
: } else {
| d**********6
发帖数: 4434 | 8 n/2 equivalent概念模糊啊，必须问清楚面试官
不过如果如你所说，应该不少于O(n)吧，不两两跟所有其他卡比较过，根本无法知
道该不该扔掉
【在 o****i 的大作中提到】
: 你这个目测不对，就走一遍的话，前面过去的卡就算扔掉了，后面的candidate不能和
: 前面的比较，而且这个题的意思，我的理解是如果set是(1,1,2,2,3)的话是可以过得，
: 你的算法貌似不能过这种情况，因为只有一个candidate。
| g*******g
发帖数: 50 | 9 ">n/2" => ">2.5" => ">=3"
【在 o****i 的大作中提到】
: 你这个目测不对，就走一遍的话，前面过去的卡就算扔掉了，后面的candidate不能和
: 前面的比较，而且这个题的意思，我的理解是如果set是(1,1,2,2,3)的话是可以过得，
: 你的算法貌似不能过这种情况，因为只有一个candidate。
| d**********6
发帖数: 4434 | 10 这思路应该是对的，其实就是quick sort
虽然qs的worst case是
O(n)，但大家都接受一般情况O(nlog(n))
【在 z***m 的大作中提到】
: 1. 随便一张，可以把集合分成equivalent 和non-equivalent两类
: 2. 如果equivlent类里有多于n/2个， return true； 否则扔掉equivlent的所有卡，
: 回到1.
: 3. 如果卡都扔完了，还没有多于一半的那种卡，就return false
|
|
