majority element.java

# practice_problem-DSA
leetcode-day1




# majority element-
//1.Using Boyer–Moore Majority Vote Algorithm-time complexity-O(n)

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}




// 2.Sorting Approch-Time Complexity: O(n log n)
import java.util.Arrays;

public class MajorityElement {
    public static void main(String[] args) {
        int nums[] = {1,2,2,1,1};

        Arrays.sort(nums);  // sorting

        int n = nums.length;
        System.out.println("Majority element: " + nums[n/2]);
    }
} 

//3.Brute Force approch - Time: O(n²)


public class MajorityElementBrute {
    public static void main(String[] args) {
        int nums[] = {1, 2, 2, 1, 1};
        int n = nums.length;

        for(int i = 0; i < n; i++){
            int count = 0;

            for(int j = 0; j < n; j++){
                if(nums[i] == nums[j]){
                    count++;
                }
            }

            if(count > n/2){
                System.out.println("Majority element: " + nums[i]);
                return;
            }
        }
    }
}