Tìm phần tử chiếm đa số trong mảng array.

Cho mảng arr, phần tử chiếm đa số trong mảng là phần tử xuất hiện lớn hơn hoặc bằng n/2, với n là số phần tử của mảng.

Cho ví dụ:

Input: arr = {1, 2, 4, 4, 3, 4, 5, 4} Output: 4

Input: arr =  {1, 2, 4, 3, 4, 5, 6, 2} Output: Khong ton tai

Cách 1: Simple

Sử dụng 2 vòng để kiểm tra số lần xuất hiện trong mảng của mỗi phần tử. 

public class Main {

    public static int marjoritySimple(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j])
                    count++;
            }
            if (count >= n/2) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
	    int[] arr = {1, 2, 4, 4, 3, 4, 5, 4};
	    int pos = marjoritySimple(arr, arr.length);
        System.out.println(pos == -1 ? "Khong ton tai": arr[pos]);
    }
}

Output: 4

Độ phức tạp: O(n²)

Cách 3: Sử dụng HashMap

Nhờ sử dụng cấu trúc dữ liệu bài toán ta sẽ đơn giản và ít code hơn.

public static void marjorityHashMap(int[] arr, int n) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                int count = map.get(arr[i]) +1;
                if (count >= arr.length /2) {
                    System.out.println(arr[i]);
                    return;
                } else
                    map.put(arr[i], count);

            }
            else
                map.put(arr[i],1);
        }
        System.out.println("Khong ton tai");

    }

Output: 4

Độ phức tạp: O(n)

Link source code: source

Nguồn tham khảo: geeksforgeeks