229. Majority Element II

[Tcdian]

229. Majority Element II

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

Example 1

Input: [3,2,3]
Output: [3]

Example 2

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let element1 = 0;
    let count1 = 0;
    let element2 = 0;
    let count2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === element1) {
            count1++;
        } else if (nums[i] === element2) {
            count2++;
        } else if (count1 === 0) {
            element1 = nums[i];
            count1 = 1;
        } else if (count2 === 0) {
            element2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    let times1 = 0;
    let times2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === element1) {
            times1++;
        } else if (nums[i] === element2) {
            times2++;
        }
    }
    const result = [];
    if (times1 > nums.length / 3) {
        result.push(element1);
    }
    if (times2 > nums.length / 3) {
        result.push(element2);
    }
    return result;
};

• TypeScript Solution

function majorityElement(nums: number[]): number[] {
    let element1 = 0;
    let count1 = 0;
    let element2 = 0;
    let count2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === element1) {
            count1++;
        } else if (nums[i] === element2) {
            count2++;
        } else if (count1 === 0) {
            element1 = nums[i];
            count1 = 1;
        } else if (count2 === 0) {
            element2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    let times1 = 0;
    let times2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === element1) {
            times1++;
        } else if (nums[i] === element2) {
            times2++;
        }
    }
    const result: number[] = [];
    if (times1 > nums.length / 3) {
        result.push(element1);
    }
    if (times2 > nums.length / 3) {
        result.push(element2);
    }
    return result;
};