subject

• Given an array of size n, find most of its elements. Most elements refer to elements that appear more than ⌊ n/2 ⌋ in the array.

• You can assume that the array is non empty and that there are always many elements in a given array.

Example 1:

Input:[3,2,3]
Output: 3

Example 2:

Input:[2,2,1,1,1,2,2]
Output: 2

Problem solution

Solution I (Hashi method)

• A hash map is used to store each element and the number of occurrences. For each key value pair in the hash map, the key represents an element and the value represents the number of occurrences of the element.

• We use a loop to traverse the array nums and add each element in the array to the hash map. After that, we traverse all key value pairs in the hash map and return the key with the largest value.

The usage of HashMap API is as follows, Jump link

code:

package leetcodePlan.Base;

import java.util.HashMap;
import java.util.Map;

public class P0169 {

	public static void main(String[] args) {

		int []  nums =  {2,2,1,1,1,2,2} ;
		System.out.println(fun(nums));
				
		}
	
	public static Map<Integer,Integer> countNums(int [] nums){
		Map<Integer,Integer> counts = new HashMap<Integer,Integer>() ;
		for(int num :nums) {
			if(!counts.containsKey(num))  { // Determine whether there are existing values in the hash table
				counts.put(num,1) ;
			} else {
				counts.put(num, counts.get(num) + 1) ;
			}
		}
		return counts ;
	}
	
	
	public static int fun(int [] nums) {
		Map<Integer,Integer> counts = countNums(nums) ;
		
		// Get the desired value from the hash table
		Map.Entry<Integer, Integer> majorityEntry = null ;
		
		for(Map.Entry<Integer, Integer> entry : counts.entrySet()) {
			if(majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
				majorityEntry = entry ;
			}
		}
		
		// Return in a way similar to the challenge arena
		
		return majorityEntry.getKey() ;
	}

}

Solution 2 (ranking method)

• Since there are elements with occurrences > ⌊ n/2 ⌋ in the array, the same elements are always adjacent in the ordered array.

• That is, there is a long string of continuous subarrays composed of the same elements with a len gt h of > ⌊ n/2 ⌋.

• Whether it is 1 1 1 2 3, 0 1 1 1 2 or - 1 0 1 1 1 1, the element in the middle of the array is always "most elements". After all, its len gt h is > ⌊ n/2 ⌋.

code:

	public static int fun2(int [] nums) {
		Arrays.sort(nums);
		return nums[nums.length >> 1] ;    // length / 2
	}

Solution III (molar voting)

• The candidate (can_num) is initialized to num [0], and the number of votes count is initialized to 1.
• When encountered with can_ Num is the same number, then the number of votes count = count + 1, otherwise the number of votes count = count - 1.
• When the number of votes count is 0, replace the candidate and reset the number of votes count to 1.
  After traversing the array, can_ Num is the final answer.

The reason is:

• The voting method is the same number of votes + 1 and different number of votes - 1. The number of "most elements" is > ⌊ n/2 ⌋, and the sum of the number of other elements is < = ⌊ n/2 ⌋.
  Therefore, the result of the sum of the number of "most elements" - the number of other elements must be > = 1.
  This is equivalent to each "majority element" and other elements offsetting each other, and at least one "majority element" must remain in the end.

• Whether the array is 1 2 1 2 1, or 1 2 2 1 1, you can always get the right candidate.

code:

	public static int fun3(int [] nums) {
		
		int cand_num = nums[0] ,count = 1 ;
		for(int i = 1 ; i < nums.length ; i++) {
			if(cand_num == nums[i]) {
				count ++ ;
			} else if(--count ==0) {
				cand_num = nums[i] ;
				count = 1;
			}
		}
		
		return cand_num ;
	}