Majority Element II (Moore vote algorithm

向右看齐 2022-05-28 06:36 109阅读 0赞

Given an integer array of size n, find all elements that appear more than `⌊ n/3 ⌋` times. The algorithm should run in linear time and in O(1) space.

题目要我们在大小为n的数组中找出所有出现次数大于n/3的数。既然是要大于n/3则一个数组中就只能最多有2个数的出现次数会大于n/3次

这题考的是Moore voting算法，就是遍历数组，先让major为数组中的第一个数，如果出现了与major相同的数字，我们就让count自加，如果不同就让count自减，如果count变为0了，这个major就换成当前遍历到的那个数。最后major中存的就是在数组中出现次数大于n/2的元素

class Solution {
    	public List<Integer> majorityElement(int[] nums) {
    		List<Integer> ls = new ArrayList<>();
    		int major = 0;
    		int count = 0;
    		int major1 = 0;
    		int count1 = 0;
    
    		for (int i = 0; i < nums.length; i++) {
    			if (nums[i] == major)
    				count++;
    			else if (nums[i] == major1)
    				count1++;
    			else if (count == 0) {
    				major = nums[i];
    				count++;
    			} else if (count1 == 0) {
    				major1 = nums[i];
    				count1++;
    			} else {
    				count--;
    				count1--;
    			}
    		}
    		
    		count = 0;
    		count1 = 0;
    		
    		for (int i=0; i<nums.length; i++) {
    			if (nums[i] == major)
    				count++;
    			if (nums[i] == major1)
    				count1++;
    		}
    		
    		if (count > nums.length/3)
    			ls.add(major);
    		if (count1 > nums.length/3) {
    			if (major != major1)
    				ls.add(major1);
    		}
    		
    		return ls;
    			
    	}
    }

当然这题只有66个测试数据，用hashmap来存数字和count也是绰绰有余的，可用map来水一波

public List<Integer> majorityElement(int nums[]) {
    		int size = nums.length;
    		HashMap<Integer, Integer> hm = new HashMap<>();
    		List<Integer> l = new ArrayList<>();
    		
    		for (int i=0; i<size; i++) {
    			hm.put(nums[i], hm.getOrDefault(nums[i], 0) + 1);
    		}
    		
    		for (Map.Entry<Integer, Integer> e : hm.entrySet()) {
    			if (e.getValue() > size/3) {
    				System.out.println(e);
    				l.add(e.getKey());
    			}
    		}
    		
    		for (int x : l) {
    			System.out.println(l);
    		}
    		
    		return l;
    	}