LeetCode //C - 229. Majority Element II

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
 

Example 1:

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

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

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

Constraints:

• $1<=nums.length<=5\ast 10^4$
• $-10^9<=nums[i]<=10^9$

From: LeetCode
Link: 229. Majority Element II

---

Solution:

Ideas:

1. Initialization: We initialize two candidates with any two different values and their counts to 0. This ensures that our algorithm doesn’t falsely initialize both candidates to the same value.

2. First Pass: We iterate through the array to find up to two potential candidates for the majority elements.

• If the current element matches one of the candidates, we increment its count.
• If the current element does not match either candidate and one of the counts is zero, we update that candidate and reset its count.
• If the current element does not match either candidate and both counts are non-zero, we decrement both counts.

3. Second Pass: We verify if the candidates we found in the first pass actually appear more than ⌊n/3⌋ times.
4. Result Construction: We construct the result array with the verified candidates.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* majorityElement(int* nums, int numsSize, int* returnSize) {
    if (numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    int candidate1 = 0, candidate2 = 1; // Initialize candidates to any two different values
    int count1 = 0, count2 = 0;

    // 1st pass: find potential candidates
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate1) {
            count1++;
        } else if (nums[i] == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = nums[i];
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = nums[i];
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    // 2nd pass: verify candidates
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate1) {
            count1++;
        } else if (nums[i] == candidate2) {
            count2++;
        }
    }

    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;

    if (count1 > numsSize / 3) {
        result[*returnSize] = candidate1;
        (*returnSize)++;
    }
    if (count2 > numsSize / 3) {
        result[*returnSize] = candidate2;
        (*returnSize)++;
    }

    return result;
}

原文地址：https://blog.csdn.net/navicheung/article/details/140454876

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！