整数数组是否存在出现次数超过一半的元素java

可以使用摩尔投票算法来解决这个问题，时间复杂度为O(n)，空间复杂度为O(1)。具体做法是假设第一个元素是超过一半的元素，然后遍历数组，如果遇到相同的元素则计数器加1，否则计数器减1，当计数器为0时，将下一个元素作为假设的超过一半的元素。最后再遍历一遍数组，判断假设的元素是否真的超过一半即可。下面是Java代码实现：

public int majorityElement(int[] nums) {
    int count = 0;
    int candidate = nums[0];
    for (int num : nums) {
        if (num == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = num;
                count = 1;
            }
        }
    }
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }
    return count > nums.length / 2 ? candidate : -1;
}

其中，-1表示不存在超过一半的元素。

相关问题

整数数组是否存在出现次数超过一半的元素，先对a中元素进行递增排序，再求出现次数最多的次数magnum，最后判断其是否符合条件

这种方法的时间复杂度为O(nlogn)，因为需要对数组进行排序。但是在求出现次数最多的元素时可以使用HashMap来优化，时间复杂度可以降到O(n)。下面是Java代码实现：

public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    int magnum = 1, count = 1, candidate = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            count++;
        } else {
            if (count > magnum) {
                magnum = count;
                candidate = nums[i - 1];
            }
            count = 1;
        }
    }
    if (count > magnum) {
        magnum = count;
        candidate = nums[nums.length - 1];
    }
    return magnum > nums.length / 2 ? candidate : -1;
}

其中，-1表示不存在超过一半的元素。

有一个含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)。