3ms Java solution using sort(), O(1) space


  • -1
    O
    public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Arrays.sort(nums);
        ArrayList<Integer> ans = new ArrayList();
        int numsLen = nums.length;
        if (numsLen == 0) return ans;
        
        int temp = nums[0];
        int i = 0;
        while (i < numsLen - numsLen / 3) {
            if (nums[i] == nums[i + numsLen / 3]) { // for majority element, it continuously exists between after sorted
                temp = nums[i];
                ans.add(temp);
                i += numsLen / 3;
                while (i < numsLen - numsLen / 3 && nums[i] == temp) i++;
            } else i++;
        }
        return ans;
    }
    

    }


  • 0
    M

    @ollie the moment you sorted it, it became O(nlogn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.