有一个含n个整数的数组a，判断其中是否存在出现次数超过所有元素一半的元素

可以使用摩尔投票算法（Boyer-Moore Majority Vote Algorithm）来解决这个问题。该算法的基本思想是，用一个计数器来记录当前元素的出现次数，如果下一个元素与当前元素相同，则计数器加1，否则计数器减1。当计数器为0时，重新选择当前元素。

最后剩下的元素可能是出现次数超过一半的元素，需要遍历整个数组统计其出现次数来进行验证。

以下是C++实现代码：

bool hasMajorityElement(vector<int>& nums) {
    int count = 0;
    int majority = 0;
    for (int num : nums) {
        if (count == 0) {
            majority = num;
        }
        count += (num == majority) ? 1 : -1;
    }
    count = 0;
    for (int num : nums) {
        if (num == majority) {
            count++;
        }
    }
    return count > nums.size() / 2;
}

时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

给定一个含n个整数的数组A，请找到数组中从未出现过的最小正整数

好的，这是一个常见的算法问题。我可以提供一种解法：

遍历数组A，将所有小于等于0的数以及大于数组长度n的数都变为1。接下来，遍历数组A，将A[i]对应的位置上的数取相反数。最后再遍历一遍数组A，找到第一个正数所在的位置，该位置+1即为从未出现过的最小正整数。

以下是该算法的Python代码实现：

def find_smallest_positive_integer(arr):
    n = len(arr)
    for i in range(n):
        if arr[i] <= 0 or arr[i] > n:
            arr[i] = 1
    for i in range(n):
        index = abs(arr[i]) - 1
        if arr[index] > 0:
            arr[index] = -arr[index]
    for i in range(n):
        if arr[i] > 0:
            return i + 1
    return n + 1

注意，这个算法的时间复杂度为O(n)，空间复杂度为O(1)。

给定一个含n个整数的数组a，请找到数组中从未出现过的最小正整数

首先，我们可以将数组a中的所有负数和零都去掉，因为它们不可能是最小正整数。

然后，我们可以将数组a中的所有正整数按照从小到大的顺序排序。

接着，我们从1开始遍历这个排序后的数组，如果当前的数不等于遍历到的位置，那么这个数就是从未出现过的最小正整数。

如果遍历完整个数组都没有找到这样的数，那么最小正整数就是数组长度加1。

代码实现如下：

def find_smallest_positive_integer(a):
    # 去掉负数和零
    a = [x for x in a if x > 0]
    # 排序
    a.sort()
    # 遍历数组
    for i, x in enumerate(a):
        if x != i + 1:
            return i + 1
    # 如果遍历完整个数组都没有找到，那么最小正整数就是数组长度加1
    return len(a) + 1

例如，对于数组a=[3, 4, -1, 1, 2, 5, 7, 0, 8]，从未出现过的最小正整数是6，因此调用find_smallest_positive_integer(a)会返回6。