一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 448|回复: 5
收起左侧

[算法题] Majority III 这道题在counters == k的时候为什么要removeKey?

[复制链接] |试试Instant~ |关注本帖
menderr 发表于 2015-9-29 22:22:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
lintcode原题在这里http://www.lintcode.com/en/problem/majority-number-iii/#
看答案,这个counters == k的时候remove key 没看懂,去掉这段,oj 也能跑通,能帮忙解释一下吗?

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: As described
     * @return: The majority number
     */
    public int majorityNumber(ArrayList<Integer> nums, int k) {
        // write your code
        HashMap<Integer, Integer> counters = new HashMap<Integer, Integer>();
        for (Integer i : nums) {
            if (!counters.containsKey(i)) {
                counters.put(i, 1);
            } else {
                counters.put(i, counters.get(i) + 1);
            }

            if (counters.size() >= k) {
                removeKey(counters);
            }
        }

        // corner case
        if (counters.size() == 0) {
            return Integer.MIN_VALUE;
        }

        // recalculate counters
        for (Integer i : counters.keySet()) {
            counters.put(i, 0);
        }
        for (Integer i : nums) {
            if (counters.containsKey(i)) {
                counters.put(i, counters.get(i) + 1);
            }
        }

        // find the max key
        int maxCounter = 0, maxKey = 0;
        for (Integer i : counters.keySet()) {
            if (counters.get(i) > maxCounter) {
                maxCounter = counters.get(i);
                maxKey = i;
            }
        }

        return maxKey;
    }

    private void removeKey(HashMap<Integer, Integer> counters) {
        Set<Integer> keySet = counters.keySet();
        List<Integer> removeList = new ArrayList<>();
        for (Integer key : keySet) {
            counters.put(key, counters.get(key) - 1);
            if (counters.get(key) == 0) {
                removeList.add(key);
            }
        }
        for (Integer key : removeList) {
            counters.remove(key);
        }
    }
}


stellari 发表于 2015-9-30 15:02:37 | 显示全部楼层
Majority的主要思想是:每次拿出k个不同元素,扔掉。那么最后总共至多会扔floor(N/k)次。如果有一个元素m出现的次数严格大于floor(N/k)次,那么扔完这floor(N/k)次后,m元素必定在剩下的N % k个元素中还有剩余。我们分别检查剩下的N % k个数是不是k-majority即可。

counters.size()>=k那一段的意思是:如果现在有k个或超过k个不同元素可以扔掉,那么我们就先扔一轮。最后剩下扔不了的N % k个元素会留在map中,然后分别检查map中每个元素是否为k-majority即可。

去掉这段代码的话,就无法扔掉任何元素。到最后所有的N个元素都在map里,就等于是统计所有元素的个数,然后找出最大的那个。这就退化成了O(N)内存的naive算法。过当然能过,但是和现在这个O(k)内存的算法比当然不够优化。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

 楼主| menderr 发表于 2015-9-30 23:51:54 | 显示全部楼层
stellari 发表于 2015-9-30 15:02
Majority的主要思想是:每次拿出k个不同元素,扔掉。那么最后总共至多会扔floor(N/k)次。如果有一个元素m出 ...

多谢,这下明白了。
回复 支持 反对

使用道具 举报

ohshire 发表于 2015-10-3 10:07:50 | 显示全部楼层
stellari 发表于 2015-9-30 15:02
Majority的主要思想是:每次拿出k个不同元素,扔掉。那么最后总共至多会扔floor(N/k)次。如果有一个元素m出 ...

终于搞明白了,多谢!
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-10-7 14:08:05 | 显示全部楼层
本帖最后由 七夜雪 于 2015-10-7 14:48 编辑
stellari 发表于 2015-9-30 15:02
Majority的主要思想是:每次拿出k个不同元素,扔掉。那么最后总共至多会扔floor(N/k)次。如果有一个元素m出 ...


这个算法的amortized time complexity应该是O(N)吧?每个element最多被加入hashmap一次然后被删掉一次。

而且我感觉上面的算法在find the max key那个部分有bug...因为那部分只是在建好的hashmap里面找counter最大的key。实际上正确的方法应该是重新traverse list然后看hashmap现有的elements哪个出现了N/k次。

回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-8 15:22:27 | 显示全部楼层
七夜雪 发表于 2015-10-7 14:08
这个算法的amortized time complexity应该是O(N)吧?每个element最多被加入hashmap一次然后被删掉一次 ...

当然是O(n)时间。我之前说的是空间复杂度。

lintcode上的题是假设1/k majority一定存在,所以出现次数最多的那个一定是答案。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表