LeetCode:面试题 17.10. 主要元素(C语言)

阳光穿透心脏的1/2处 2023-02-21 14:15 19阅读 0赞

**题目描述 ：**  
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：\[1,2,5,9,5,9,5,5,5\]  
输出：5

示例 2：

输入：\[3,2\]  
输出：-1

示例 3：

输入：\[2,2,1,1,1,2,2\]  
输出：2

说明：  
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-majority-element-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

int majorityElement(int* nums, int numsSize)
    { 
        int count = 1;
        int major = nums[0];
        int i = 0;
    
        for(i = 1;i < numsSize;i++)
        { 
            if(major == nums[i])
            { 
                count++;
            }
            else
            { 
                count--;
            }
    
            if(0 == count)
            { 
                count = 1;
                major = nums[i];
            }
        }
    
        for(i = 0; i < numsSize;i++)
        { 
            if(major == nums[i])
            { 
                count++;
            }
        }
    
        return count > numsSize / 2 ? major:-1; 
    }

**运行结果：**  
![在这里插入图片描述][20200701093801206.png]  
**Notes：**  
使用摩尔投票法。摩尔投票法适用于找出一组数字序列中出现次数大于总数1/2的数字，每次从数组中选择两个不相同的数字删掉，剩下的数字就是就是出现次数超过一半的数字。**因为数字总数要大于1/2，所以不管数组是否乱序排列，总会存在出现最多的数字相邻排列以及该数字的总数要比该数组长度的一半要长，并且只有一个符合这两个条件的数字**。另外需要注意的是相同数字的相邻长度越长并不一定意味着是出现最多的数字，比如\[5,2,5,6,5,5,1,5,1\]符合条件而\[5,2,5,6,5,5,1,1,1\]虽然1的相邻长度最长但并不满足长度占总长一半，所以不符合条件。

[20200701093801206.png]: https://img-blog.csdnimg.cn/20200701093801206.png