[LeetCode 169] Majority Element

문제 바로가기

Description

---

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1

---

• Input: nums = [3,2,3]
• Output: 3

Example 2

---

• Input: nums = [2,2,1,1,1,2,2]
• Output: 2

Constraints

---

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• The input is generated such that a majority element will exist in the array.

Code

---

내 제출

---

class Solution {
    public int majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int index = 0;

        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list);

        while (index < list.size()) {
            int qty = Collections.frequency(list, list.get(index));
            if (qty > (list.size() / 2)) {
                return list.get(index);
            }
            index += list.lastIndexOf(list.get(index)) + 1;
        }
        return 0;
    }
}

Runtime	Memory
19 ms	49.2 MB

다른 풀이

---

class Solution {
    public int majorityElement(int[] nums) {
        int  majorityElement = nums[0];
        HashMap<Integer,Integer> elements = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            
            if(elements.containsKey(nums[i])){
                elements.put(nums[i], (elements.get(nums[i])+1));
            }
            else{
                elements.put(nums[i], 1);
            }

            if(elements.get(nums[i])!=null && elements.get(nums[i])>((int)Math.ceil(nums.length/2))){
                majorityElement = nums[i];
                break;
            }
        }
        return majorityElement;
    }
}

Reference

---