leetcode 229. Majority Element II | 229. 求众数 II（找出现次数超过n/k的元素）

以你之姓@ 2022-10-08 15:22 84阅读 0赞

## 题目 ##

[https://leetcode.com/problems/majority-element-ii/][https_leetcode.com_problems_majority-element-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

> 思路来源于左程云《程序员代码面试指南》

##### 问题描述 #####

原问题：给定一个整型数组 arr，打印其中出现次数大于一半的数。  
进阶问题：给定一个整型数组 arr，再给定一个整数 K，打印所有出现次数大于 N/K 的数。

##### 要求 #####

原问题要求时间复杂度为 O(N)，额外空间复杂度为 O(1)。  
进阶问题要求时间复杂度为 O(N×K)，额外空间复杂度为 O(K)。

##### 解答 #####

无论是原问题还是进阶问题，都可以用哈希表记录每个数及其出现的次数，但是额外空间复杂度为 O(N)，不符合题目要求，所以本文不再详述这种简单的方法。本文提供方法的核心思路是，**一次在数组中删掉 K 个不同的数，不停地删除，直到剩下数的种类不足 K 就停止删除，那么，如果一个数在数组中出现的次数大于 N/K，则这个数最后一定会被剩下来**。

一次在数组中删掉 K 个不同的数，不停地删除，直到剩下的数的种类不足 K，那么，如果某些数在数组中出现次数大于 N/K，则这些数最后一定会被剩下来。原问题中，我们解决了找到出现次数超过 N/2 的数，解决的办法是立了 1 个候选 cand，以及这个候选的 times 统计。进阶问题具体的实现也类似，只要立 K-1 个候选，然后有 K-1 个 times 统计即可，具体过程如下。

遍历到 arr\[i\] 时，看 arr\[i\] 是否与已经被选出的某一个候选相同。

*  如果与某一个候选相同，就把属于那个候选的点数统计加 1。
 *  如果与所有的候选都不相同，先看当前的候选是否选满了，K-1 就是满，否则就是不满：
    
     *  如果不满，把 arr\[i\]作为一个新的候选，属于它的点数初始化为 1。
     *  如果已满，说明此时发现了 K 个不同的数，arr\[i\]就是第 K 个。此时把每一个候选各自的点数全部减 1，表示每个候选“付出”一个自己的点数。如果某些候选的点数在减1 之后等于 0，则还需要把这些候选都删除，候选又变成不满的状态。

在遍历过程结束后，再遍历一次 arr，验证被选出来的所有候选有哪些出现次数真的大于N/K，打印符合条件的候选。具体请参看如下代码中的 printKMajor 方法。

package chapter_8_arrayandmatrix;
    
    import java.util.Arrays;
    
    public class Problem_20_PrintMaxTopK { 
    
    	public static class HeapNode { 
    		public int value; // 值是什么
    		public int arrNum; // 来自哪个数组
    		public int index; // 来自数组的哪个位置
    
    		public HeapNode(int value, int arrNum, int index) { 
    			this.value = value;
    			this.arrNum = arrNum;
    			this.index = index;
    		}
    	}
    
    	public static void printTopK(int[][] matrix, int topK) { 
    		int heapSize = matrix.length;
    		HeapNode[] heap = new HeapNode[heapSize];
    		for (int i = 0; i != heapSize; i++) { 
    			int index = matrix[i].length - 1;
    			heap[i] = new HeapNode(matrix[i][index], i, index);
    			heapInsert(heap, i);
    		}
    		System.out.println("TOP " + topK + " : ");
    		for (int i = 0; i != topK; i++) { 
    			if (heapSize == 0) { 
    				break;
    			}
    			System.out.print(heap[0].value + " ");
    			if (heap[0].index != 0) { 
    				heap[0].value = matrix[heap[0].arrNum][--heap[0].index];
    			} else { 
    				swap(heap, 0, --heapSize);
    			}
    			heapify(heap, 0, heapSize);
    		}
    	}
    
    	public static void heapInsert(HeapNode[] heap, int index) { 
    		while (index != 0) { 
    			int parent = (index - 1) / 2;
    			if (heap[parent].value < heap[index].value) { 
    				swap(heap, parent, index);
    				index = parent;
    			} else { 
    				break;
    			}
    		}
    	}
    
    	public static void heapify(HeapNode[] heap, int index, int heapSize) { 
    		int left = index * 2 + 1;
    		int right = index * 2 + 2;
    		int largest = index;
    		while (left < heapSize) { 
    			if (heap[left].value > heap[index].value) { 
    				largest = left;
    			}
    			if (right < heapSize && heap[right].value > heap[largest].value) { 
    				largest = right;
    			}
    			if (largest != index) { 
    				swap(heap, largest, index);
    			} else { 
    				break;
    			}
    			index = largest;
    			left = index * 2 + 1;
    			right = index * 2 + 2;
    		}
    	}
    
    	public static void swap(HeapNode[] heap, int index1, int index2) { 
    		HeapNode tmp = heap[index1];
    		heap[index1] = heap[index2];
    		heap[index2] = tmp;
    	}
    
    	public static int[][] generateRandomMatrix(int maxRow, int maxCol,
    			int maxValue) { 
    		if (maxRow < 0 || maxCol < 0) { 
    			return null;
    		}
    		int[][] matrix = new int[(int) (Math.random() * maxRow) + 1][];
    		for (int i = 0; i != matrix.length; i++) { 
    			matrix[i] = new int[(int) (Math.random() * maxCol) + 1];
    			for (int j = 0; j != matrix[i].length; j++) { 
    				matrix[i][j] = (int) (Math.random() * maxValue);
    			}
    			Arrays.sort(matrix[i]);
    		}
    		return matrix;
    	}
    
    	public static void printMatrix(int[][] matrix) { 
    		for (int i = 0; i != matrix.length; i++) { 
    			for (int j = 0; j != matrix[i].length; j++) { 
    				System.out.print(matrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    
    	public static void main(String[] args) { 
    		int[][] matrix = generateRandomMatrix(5, 10, 1000);
    		printMatrix(matrix);
    		System.out.println("===========================");
    		printTopK(matrix, 100);
    	}
    }

##### 本题代码 #####

import java.util.ArrayList;
    import java.util.List;
    
    class Solution { 
        public List<Integer> majorityElement(int[] nums) { 
            ArrayList<Integer> list = new ArrayList<>();
            if (nums.length <= 2) { 
                list.add(nums[0]);
                if (nums.length == 2 && nums[0] != nums[1]) list.add(nums[1]);
                return list;
            }
            int n1 = Integer.MAX_VALUE;
            int n2 = Integer.MAX_VALUE;
            int n3 = Integer.MAX_VALUE;
            int c1 = 0; // count n1
            int c2 = 0;
            int c3 = 0;
            for (int n : nums) { 
                if (n == n1) c1++;
                else if (n == n2) c2++;
                else if (n == n3) c3++;
                else { 
                    if (c1 == 0) { 
                        n1 = n;
                        c1 = 1;
                    } else if (c2 == 0) { 
                        n2 = n;
                        c2 = 1;
                    } else if (c3 == 0) { 
                        n3 = n;
                        c3 = 1;
                    } else { 
                        c1--;
                        c2--;
                        c3--;
                    }
                }
            }
            c1 = c2 = c3 = 0;
            for (int n : nums) { 
                if (n == n1) c1++;
                else if (n == n2) c2++;
                else if (n == n3) c3++;
            }
            if (c1 > nums.length / 3) list.add(n1);
            if (c2 > nums.length / 3) list.add(n2);
            if (c3 > nums.length / 3) list.add(n3);
            return list;
        }
    }

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

[https_leetcode.com_problems_majority-element-ii]: https://leetcode.com/problems/majority-element-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/06dc679d6eaf4e809cf96624e02d9e83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/bc6d447d1a214f3fbde523f66086c38b.png