已知一个整数序列A=（a0，a1，…an），如果其中有一个元素的出现次数超过n/2，就称该元素为A的主元素，否则就称整数序列没有主元素。例如A=（0，5，5，3，5，7，5，5），则5为主元素。A=（0，5，5，3，5，1，5，7），则A中没有主元素。要求编写程序实现寻找给定整数序列的主元素，如果找到，则输出主元素。如果没有找到，则输出-1 C++

<think>好的，我现在需要解决这个问题：找出一个整数序列的主元素，如果存在的话。主元素的定义是出现次数超过n/2的元素，其中n是序列的长度。如果不存在这样的元素，就返回-1。我需要用C++来实现这个功能。 首先，我得理解问题。主元素必须出现次数超过一半，也就是次数大于n/2。例如，当n=8时，主元素至少需要出现5次。那怎么高效地找到这样的元素呢？ 我想到几种可能的解决方法。第一种方法是暴力法，遍历每个元素，统计每个元素出现的次数，然后检查是否有超过n/2的。但这样的话，时间复杂度是O(n²)，当n很大时效率会很低。比如，对于每个元素都要遍历整个数组，这显然不够优化。 那有没有更高效的方法呢？记得之前学过摩尔投票算法（Boyer-Moore Majority Vote Algorithm），这个算法可以在O(n)时间复杂度和O(1)空间复杂度下找到可能的主元素。不过，这个算法有一个前提，就是必须存在主元素，否则需要再遍历一次确认。这可能适合这个问题。 摩尔投票算法的基本思想是，每次从序列中选择两个不同的元素删除，直到剩下的元素都相同，那么这个元素可能就是主元素。具体实现时，可以用两个变量：一个保存当前候选元素，另一个记录次数。遍历数组时，如果次数为0，就选择当前元素作为候选；如果当前元素等于候选元素，次数加1，否则次数减1。遍历结束后，候选元素可能为主元素，但需要再次遍历确认其出现次数是否真的超过n/2。 那具体怎么实现呢？步骤大概是这样的： 1. 初始化候选元素和计数器。候选元素初始可以是任意值，计数器设为0。 2. 遍历数组中的每个元素： a. 如果计数器为0，将当前元素设为候选，计数器设为1。 b. 否则，如果当前元素等于候选元素，计数器加1。 c. 否则，计数器减1。 3. 遍历结束后，再次遍历数组统计候选元素的出现次数，检查是否超过n/2。 4. 如果超过，返回候选元素；否则返回-1。 这个算法的时间复杂度是O(n)，空间复杂度是O(1)，符合题目要求。 那现在需要考虑特殊情况。比如，当数组为空的时候怎么办？题目中给出的例子都是非空的，但实际程序中可能需要处理这种情况。如果数组为空，应该返回-1。另外，如果所有元素都相同的情况，比如数组长度为5，元素全是3，那么3的出现次数是5，超过5/2=2.5，所以是主元素。这时候算法是否能正确处理？ 举个例子，假设数组是[3,3,3,3,3]。第一次遍历时，候选元素初始为0，但第一个元素是3，计数器变为1。接下来每个元素都是3，计数器递增到5。最后候选元素是3，统计次数是5，超过2.5，正确返回3。 另一个例子是数组中没有主元素的情况，比如A=[0,5,5,3,5,1,5,7]，长度为8，主元素需要出现至少5次。在这个数组中，5出现了4次，所以不满足。算法在第一次遍历得到的候选元素可能是什么？ 假设按照步骤来，初始候选元素为0，计数器为0。第一个元素是0，计数器变为1。第二个元素是5，不等于候选元素，计数器减到0。第三个元素是5，此时计数器是0，设为候选，计数器为1。接下来的元素3，不等于候选，计数器减到0。第四个元素5，设为候选，计数器1。第五个元素1，计数器减0。然后第五个元素5，设为候选，计数器1。第六个元素7，计数器减0。遍历结束后的候选元素是7？或者可能中间步骤不同？ 或者可能需要具体走一遍这个例子。比如数组是0,5,5,3,5,1,5,7： 初始候选是None，计数器0。 第一个元素0，计数器变为1，候选是0。 第二个元素5，不等于候选，计数器0。此时候选无效？ 第三个元素5，此时计数器0，候选变为5，计数器1. 第四个元素3，不等于5，计数器0. 第五个元素5，计数器0，候选变为5，计数器1. 第六个元素1，不等于5，计数器0. 第七个元素5，计数器0，候选变为5，计数器1. 第八个元素7，不等于5，计数器0. 遍历结束后候选元素是5。这时候需要再次统计5的出现次数。原数组中5出现的次数是4次，而n=8，所以4没有超过4，所以应该返回-1。所以算法在第一次遍历得到的候选元素可能不是真正的主元素，这时候必须再次验证。 这说明，摩尔投票法只能找到可能的候选元素，但必须再遍历一次确认。 那现在具体到代码实现上： 首先，函数需要接收数组，比如一个vector<int>或者数组，以及长度n。然后按照上述步骤处理。 在代码中： 步骤一：找到候选元素。 初始化candidate为-1，count为0。 遍历数组中的每个数： 如果count为0，则将当前数设为candidate，count设为1。 否则，如果当前数等于candidate，count++；否则count--. 步骤二：验证候选元素的出现次数是否超过n/2. 统计数组中等于candidate的元素个数，如果超过n/2，返回candidate，否则返回-1. 那需要注意的是，当原数组全为同一元素时，这个算法也能正确找到，比如例子中的全5的情况。但如果数组中没有主元素，比如上面例子中的情况，候选元素可能被错误地选为某个元素，但验证步骤会发现次数不够。 现在需要考虑当数组为空时的情况。例如n=0时，应该直接返回-1。所以在代码开始时需要处理这种情况。 现在编写代码的大致结构： int findMajorityElement(vector<int>& nums) { int n = nums.size(); if (n == 0) return -1; // 步骤一：找到候选元素 int candidate = -1; int count = 0; for (int num : nums) { if (count == 0) { candidate = num; count = 1; } else { if (num == candidate) { count++; } else { count--; } } } // 步骤二：验证候选元素是否为主元素 int cnt = 0; for (int num : nums) { if (num == candidate) { cnt++; } } if (cnt > n / 2) { return candidate; } else { return -1; } } 这样应该可以实现功能。现在需要测试几个例子。 比如第一个例子A=（0，5，5，3，5，7，5，5），n=8。候选元素应该是5吗？ 在遍历时： 初始count=0，第一个元素0设为候选，count=1. 第二个元素5，不等于候选，count减到0. 第三个元素5，count=0，设为候选，count=1. 第四个元素3，不等于候选，count减到0. 第五个元素5，设为候选，count=1. 第六个元素7，不等于，count减到0. 第七个元素5，设为候选，count=1. 第八个元素5，等于，count增加到2. 所以候选元素是5。统计次数：原数组中有5出现的次数是5次，超过4，所以返回5。正确。 第二个例子A=（0，5，5，3，5，1，5，7），n=8。遍历过程： 初始count=0，候选设为0，count=1. 第二个元素5，count减到0. 第三个元素5，候选设为5，count=1. 第四个元素3，count减到0. 第五个元素5，候选设为5，count=1. 第六个元素1，count减到0. 第七个元素5，候选设为5，count=1. 第八个元素7，count减到0. 所以候选元素是7？或者可能是最后一步？ 或者，我需要再详细模拟一遍第二个例子： 数组元素依次是0,5,5,3,5,1,5,7. 遍历过程： i=0，元素0： count=0，所以candidate=0，count=1. i=1，元素5： 不等于candidate 0，count减到0. i=2，元素5： 此时count是0，所以candidate=5，count=1. i=3，元素3： 不等于5，count减到0. i=4，元素5： count=0，candidate=5，count=1. i=5，元素1： 不等于5，count减到0. i=6，元素5： count=0，candidate=5，count=1. i=7，元素7： 不等于5，count减到0. 遍历结束后，candidate是5吗？因为当i=6的时候，count是1，然后i=7的时候元素7，count减到0。此时循环结束，candidate是5吗？或者，在最后一次迭代时，元素7的处理导致count变为0，此时循环结束后的candidate是5吗？ 是的。因为在处理i=7时，当前candidate是5，count是1。元素7不等于5，所以count减到0。此时循环结束。此时，candidate仍然是5，因为最后一次操作是count减到0，但candidate不会被改变。只有当count为0的时候，下一个元素才会改变candidate。所以遍历结束后，candidate是5。然后验证时，统计数组中5的出现次数：在数组中，元素0、5、5、3、5、1、5、7。出现次数是4次？因为元素下标i=1是5，i=2是5，i=4是5，i=6是5。共四次。4不大于4（n=8，n/2=4），所以返回-1。这样代码就能正确返回-1。 这说明算法是正确的。那这个代码是正确的。 那现在需要考虑一些特殊情况，例如数组长度为1的情况。例如，数组只有元素3，此时n=1，主元素需要出现次数超过0.5，也就是至少1次。此时候选元素是3，统计次数是1，返回3。这没问题。 另一个例子是所有元素都相同，例如数组长度5，元素全为2。此时候选元素会被正确找到，统计次数为5>2.5，返回2。 那代码的正确性应该没有问题。 综上，这个算法是正确的，而且满足时间复杂度的要求。因此，可以用这种方法来解决问题。</think>以下是寻找主元素的C++实现，采用摩尔投票算法，时间复杂度为$O(n)$，空间复杂度为$O(1)$： ```cpp #include <vector> using namespace std; int findMajorityElement(vector<int>& nums) { int n = nums.size(); if (n == 0) return -1; // 第一阶段：找到候选元素 int candidate = -1; int count = 0; for (int num : nums) { if (count == 0) { candidate = num; count = 1; } else { if (num == candidate) count++; else count--; } } // 第二阶段：验证候选元素是否为主元素 int verifyCount = 0; for (int num : nums) { if (num == candidate) verifyCount++; } return (verifyCount > n/2) ? candidate : -1; } ``` ### 算法步骤解析 1. **初始化候选元素** 使用`candidate`存储可能的候选元素，`count`记录相对数量差。遍历时若`count`归零，则更新候选元素。 2. **摩尔投票过程** - 当`count`为0时，当前元素成为新候选，`count`设为1 - 遇到相同元素时`count++`，不同元素时`count--` - 核心思想：通过抵消不同元素，最终剩下的候选可能为主元素 3. **二次验证** 由于算法可能误判不存在主元素的情况（如[A,B,A,C]），需再次遍历统计候选元素的实际出现次数，严格验证是否超过$n/2$。 ### 复杂度分析 - **时间复杂度**：两次线性遍历，总时间复杂度为$O(2n) \rightarrow O(n)$ - **空间复杂度**：仅使用固定数量的变量，为$O(1)$ ### 示例测试 ```cpp int main() { vector<int> test1 = {0,5,5,3,5,7,5,5}; // 应返回5 vector<int> test2 = {0,5,5,3,5,1,5,7}; // 应返回-1 vector<int> test3 = {3}; // 应返回3 cout << findMajorityElement(test1) << endl; // 输出5 cout << findMajorityElement(test2) << endl; // 输出-1 cout << findMajorityElement(test3) << endl; // 输出3 return 0; } ``` 该算法高效可靠，能正确处理空数组、全同元素、交替出现等边界情况，是解决主元素问题的最优解法。