Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

169. Majority Element #94

Open
Tcdian opened this issue Apr 2, 2020 · 1 comment
Open

169. Majority Element #94

Tcdian opened this issue Apr 2, 2020 · 1 comment

Comments

@Tcdian
Copy link
Owner

Tcdian commented Apr 2, 2020

169. Majority Element

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于  ⌊ n/2 ⌋ 的元素。

Example 1

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

Example 2

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

Note

  • 你可以假设数组是非空的,并且给定的数组总是存在多数元素。
@Tcdian
Copy link
Owner Author

Tcdian commented Apr 2, 2020

Solution 1 ( Hash Map )

  • JavaScript Solution
/**
 * @param {number[]} nums
 * @return {number}
 */

// 利用 hash Map 记录每个元素出现的数量,找出数量超过半数的元素

var majorityElement = function(nums) {
    const hashMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (!hashMap.has(nums[i])) {
            hashMap.set(nums[i], 0);
        }
        hashMap.set(nums[i], hashMap.get(nums[i]) + 1);
        if (hashMap.get(nums[i]) > nums.length / 2) {
            return nums[i];
        }
    }
};

Solution 2 ( Sort )

  • JavaScript Solution
/**
 * @param {number[]} nums
 * @return {number}
 */

// 将数组排序,排序后的中间位置元素即为超过半数的元素

var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
};

Solution 3 ( Divide And Conquer )

  • JavaScript Solution
/**
 * @param {number[]} nums
 * @return {number}
 */

// 利用分治的思想,分别查找拆分后的左右两边,如果两边的多数元素为同一个,则为归并后的多数元素;
// 如果不同,取整个区间数量多的为多数元素

var majorityElement = function(nums) {
    return divideAndSearch(nums, 0, nums.length - 1);

    function divideAndSearch(nums, l, r) {
        if (l === r) {
            return nums[l];
        }

        const mid = Math.floor((l + r) / 2);
        const leftMajority = divideAndSearch(nums, l, mid);
        const rightMajority = divideAndSearch(nums, mid + 1, r);

        if (leftMajority === rightMajority) {
            return leftMajority;
        }

        let leftMajorityCount = 0;
        let rightMajorityCount = 0;
        
        for (let i = l; i <= r; i++) {
            if (nums[i] === leftMajority) {
                leftMajorityCount += 1;
            }
            if (nums[i] === rightMajority) {
                rightMajorityCount += 1;
            }
        }

        return leftMajorityCount > rightMajorityCount ? leftMajority : rightMajority;
    }
};

Solution 4 ( 摩尔投票 )

  • JavaScript Solution
/**
 * @param {number[]} nums
 * @return {number}
 */

// 摩尔投票

var majorityElement = function(nums) {
    let majority = nums[0];
    let majorityVotes = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === majority) {
            majorityVotes += 1;
        } else {
            majorityVotes -= 1;
        }

        if (majorityVotes === 0) {
            majority = nums[i];
            majorityVotes = 1;
        }
    }

    return majority;
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant