961. 重复 N 次的元素

川长思鸟来 2023-02-10 05:29 16阅读 0赞

# 题目来源 #

[leetcode][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 哈希表 ##

因为一个2N个数，N+1个不同的元素：元素1重复了N次，剩下N个为N个不同的元素，也就是除了元素1有N个，其他元素都只有N个

结论1：最大元素次数为N  
结论2：次数大于2的元素就是元素N

class Solution {
        
        public int repeatedNTimes(int[] A) {
        
            Map<Integer, Integer> map = new HashMap<>();
            for (int value : A) {
        
                if (map.containsKey(value)) {
        
                    return value;
                } else {
        
                    map.put(value, 1);
                }
            }
    
            return -1;
        }
    }

![在这里插入图片描述][20200520162316942.png]

## 随机法 ##

class Solution {
        
        public int repeatedNTimes(int[] A) {
        
            Random r = new Random();
            int len = A.length;
            int a,b;
            while(true){
        
                a = r.nextInt(len);
                b = r.nextInt(len);
                if(a!=b && A[a]==A[b]){
        
                    return A[a];
                }
            }
        }
    }

摩根投票法，必须是数 > N/2的

[leetcode]: https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200520163837685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200520162316942.png]: https://img-blog.csdnimg.cn/20200520162316942.png