[笔记]《编程之美》2.3 寻找发帖“水王”

Zoey Young 算法&数据结构 算法 笔试 面试 书籍 编程之美

题目

Tango是微软亚洲研究院的一个试验项目. 研究院的员工和实习生们都很喜欢在Tango上面交流灌水. 传说, Tango有一大"水王", 他不但喜欢发贴, 还会回复其他ID发的每个帖子. 坊间风闻该"水王"发帖数目超过了帖子总数的一半. 如果你有一个当前论坛上所有帖子(包括回帖)的列表, 其中帖子作者的ID也在表中, 你能快速找出这个传说中的Tango水王吗?

思路

3, 1, 3, 1, 5, 1, 6, 1, 2, 1, 1, 1, 2

input | candidate | nTimes
      |     -1    |   0
   3  |      3    |   1
   1  |      3    |   0
   3  |      3    |   1
   1  |      3    |   0
   5  |      5    |   1
   1  |      5    |   0
   6  |      6    |   1
   1  |      6    |   0
   2  |      2    |   1
   1  |      2    |   0
   1  |      1    |   1
   1  |      1    |   2
   2  |      1    |   1

前提是“水王”的ID在ID列表中的次数超过一半，刚好等于一半是不行的

def find(A):
    candidate = -1
    nTimes = 0
    for i in range(0, len(A)):
        if nTimes == 0:
            candidate = A[i]
            nTimes += 1
        elif candidate == A[i]:
            nTimes += 1
        else:
            nTimes -=1
    return candidate

A = [3, 1, 3, 1, 5, 1, 6, 1, 2, 1, 1, 1, 2]
print(find(A))

扩展问题

随着Tango的发展, 管理员发现, "超级水王"没有了. 统计结果表明, 有3个发帖很多的ID, 他们的发帖数目都超过了帖子总数目N的1/4. 你能从发帖ID列表中快速找出他们的ID吗?

#-*-coding:utf-8-*-
def find(A):
    candidate = [-1] * 3
    nTimes = [0] * 3
    for i in range(0, len(A)):
        is_candidate = False
        for j in range(0, 3):
            # 第一种情况：A[i]不在候选项中，且有计数器为0的项，则设置A[i]为新的候选项
            if nTimes[j] == 0 and not A[i] in candidate:
                is_candidate = True
                candidate[j] = A[i]
                nTimes[j] = 1
                break
            # 第二种情况：A[i]在候选项中，则把对应计数器加1
            elif candidate[j] == A[i]:
                is_candidate = True
                nTimes[j] += 1
                break
        # 第三种情况: A[i]不在候选项中, 且没有计数器为0的项, 则所有计数器减1
        if not is_candidate:
            for j in range(0, 3):
                nTimes[j] -= 1
        # print(A[i], candidate, nTimes)
    return candidate

# A = [1, 2, 3, 2, 1, 2, 3, 3, 1, 2, 3, 6, 1, 1, 2, 3, 1, 2, 3, 8]
A = [2, 2, 3, 2, 3, 3, 1, 1, 7, 1, 1, 3, 3, 10, 6, 1, 2, 2, 2, 8, 1, 3, 10, 1, 3, 2, 8, 2, 1, 3, 9, 1, 3, 1, 3, 2, 10, 1, 2, 3, 2, 1, 4, 13, 3, 9, 2, 3, 2, 1]
# 验证用
# print(set([x for x in A if A.count(x) > len(A) / 4]))
print(find(A))

另外一种Python的简洁写法:

>>> a = [3, 1, 3, 1, 5, 1, 6, 1, 2, 1, 1, 1, 2]
>>> print set([x for x in a if a.count(x) > len(a)/2])
set([1])
>>> b = [2, 2, 3, 2, 3, 3, 1, 1, 7, 1, 1, 3, 3, 10, 6, 1, 2, 2, 2, 8, 1, 3, 10, 1, 3, 2, 8, 2, 1, 3, 9, 1, 3, 1, 3, 2, 10, 1, 2, 3, 2, 1, 4, 13, 3, 9, 2, 3, 2, 1]
>>> print set([x for x in b if b.count(x) > len(b)/4])
set([1, 2, 3])

【练习Java, 方法同上面】

【笔试题】数组中有一个数字出现的次数超过了数组长度的一半, 找出这个数字.

public class Hello {
    public static int find(int[] arr) {
        int candidate = -1;
        int ntimes = 0;
        int arr_len = arr.length;
        for (int i = 0; i < arr_len; i++) {
            if (ntimes == 0) {
                candidate = arr[i];
                ntimes++;
            } else if (arr[i] == candidate) {
                ntimes++;
            } else {
                ntimes--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] arr = { 3, 1, 3, 1, 5, 1, 6, 1, 2, 1, 1, 1, 2 };
        System.out.println(find(arr)); // 1
    }
}