Enter n integers and output the number of occurrences greater than or equal to half the length of the array

Cattle from · Written examination of Internet famous enterprises / Interview question bank

One , Title and description ：

Input n It's an integer , The number of output occurrences greater than or equal to half the length of the array

Input description ：

Each test input contains n Space separated n It's an integer ,n No more than 100, among There's an integer More than or equal to n/2.

Output description ：

The number of output occurrences is greater than or equal to n/2 Number of numbers .

Two , Example

Input

3 9 3 2 5 6 7 3 2 3 3 3

Output

3

3、 ... and , Solution ideas and code
！！！！ First, notice that there is only one such number

Ideas 1：

Sort the input sequence , The element in the middle position means that the occurrence times are greater than or equal to n/2 Number of numbers

Code ：

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
    
            String str = scanner.nextLine(); // Input received as string , And each character is separated by a space 
            String[] s = str.split(" "); // Split the string with spaces 
            int[] arr = new int[s.length]; // Prepare an array 
            for (int i = 0; i < arr.length; i++) {
    
                arr[i] = Integer.parseInt(s[i]);  // Convert the element to type and move it into the prepared array 
            }
            System.out.println(arr[arr.length/2]);// Just take out the middle element 
        }
    }
}

Ideas 2：

utilize Map Count the number of occurrences of each element , Output Value Greater than or equal to n/2 Corresponding key that will do

Code ：

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

public class Main{
    
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
    
            String str = scanner.nextLine(); // Input received as string , And each character is separated by a space 
            String[] s = str.split(" "); // Split the string with spaces 
            Integer[] arr = new Integer[s.length]; // Prepare an array （Integer best ,int It's fine too , Use at this time Map, So avoid unpacking with the packing type ）
            for (int i = 0; i < arr.length; i++) {
    
                arr[i] = Integer.parseInt(s[i]);  // Convert the element to type and move it into the prepared array 
            }
            Map<Integer,Integer> map = new HashMap<>();
            for (int j = 0; j < arr.length; j++) {
      // Count the number of each element 
                Integer count = map.get(arr[j]); // Take out the current key, Corresponding to Value
                if(count == null){
    
                    map.put(arr[j],1); // If it's the first time to put , namely Value Set as 1
                } else {
    
                   map.put(arr[j],count+1);// Otherwise, on the original basis +1
                }
            }
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
      // Traverse Map Find an array that is greater than or equal to half the length of the array Value Corresponding key
                if(entry.getValue() >= (arr.length/2)){
    
                    int x = entry.getKey();
                    System.out.println(x);
                    break;
                }
            }
        }
    }
}