题目描述

多数元素 II

在一个大小为 n 的数组 nums 中，除了某个整数出现次数超过 n/3 次之外，其他所有整数出现的次数都不超过 n/3。找出并返回那个出现次数超过 n/3 的整数。

注意：题目假设数组非空，并且给定的数组总是存在多数元素。

示例

示例 1:

输入: nums = [3,2,3]
输出: 3

示例 2:

输入: nums = [1,1,1,3,3,2,2,2]
输出: 1

PHP 示例代码

function majorityElement($nums) {
    $n = count($nums);
    $candidate1 = $candidate2 = null;
    $count1 = $count2 = 0;

    foreach ($nums as $num) {
        if ($candidate1 === null || $num === $candidate1) {
            $count1++;
            $candidate1 = $num;
        } elseif ($candidate2 === null || $num === $candidate2) {
            $count2++;
            $candidate2 = $num;
        } elseif ($count1 > 0) {
            $count1--;
        } elseif ($count2 > 0) {
            $count2--;
        }
    }

    $count1 = $count2 = 0;
    foreach ($nums as $num) {
        if ($num === $candidate1) {
            $count1++;
        } elseif ($num === $candidate2) {
            $count2++;
        }
    }

    if ($count1 > $n / 3) {
        return $candidate1;
    } elseif ($count2 > $n / 3) {
        return $candidate2;
    }

    return null; // 理论上不会执行到这里，因为题目假设总是存在多数元素
}

Python 示例代码

def majorityElement(nums):
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0

    for num in nums:
        if candidate1 is None or num == candidate1:
            count1 += 1
        elif candidate2 is None or num == candidate2:
            count2 += 1
        elif count1 > 0:
            count1 -= 1
        elif count2 > 0:
            count2 -= 1
        else:
            candidate1, candidate2 = num, num
            count1, count2 = 1, 1

    count1, count2 = 0, 0
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1

    if count1 > len(nums) // 3:
        return candidate1
    if count2 > len(nums) // 3:
        return candidate2

    return None  # 理论上不会执行到这里

JavaScript 示例代码

function majorityElement(nums) {
    let candidate1 = null, candidate2 = null;
    let count1 = 0, count2 = 0;

    for (let num of nums) {
        if (candidate1 === null || num === candidate1) {
            count1++;
            candidate1 = num;
        } else if (candidate2 === null || num === candidate2) {
            count2++;
            candidate2 = num;
        } else if (count1 > 0) {
            count1--;
        } else if (count2 > 0) {
            count2--;
        }
    }

    count1 = count2 = 0;
    for (let num of nums) {
        if (num === candidate1) {
            count1++;
        } else if (num === candidate2) {
            count2++;
        }
    }

    if (count1 > nums.length / 3) {
        return candidate1;
    } else if (count2 > nums.length / 3) {
        return candidate2;
    }

    return null; // 理论上不会执行到这里
}

以上代码示例均通过遍历数组两次来找出出现次数超过数组长度三分之一的元素。在第一次遍历中，我们使用两个候选者和对应的计数器来记录可能的多数元素。在第二次遍历中，我们统计这两个候选者的实际出现次数，并返回出现次数超过三分之一的元素。