本文共 1026 字，大约阅读时间需要 3 分钟。

【考研408真题】【leetcode】求一维数组的主元素

主元素是数组内出现次数超过一半的数字，如果有返回该数，否则返回-1，比如【4，4，4，2，3，1，4】返回4，【1，2，1，3，1，3】返回-1

解题思路很多： （1）时间复杂度达到O（n^2）：利用新数组存值，再遍历计数 （2）时间复杂度达到O（nlogn）: 先排序（比如快排时间复杂度是O（nlogn）），再判断是否有主元素，事实上如果存在主元素，那么它一定是数组的中位数，只需再遍历一遍就能知道结果 （3）时间复杂度达到O(n)： 核心思想 如果一个元素是主元素，去除一个该元素占比一半的子集，该元素在余集中占比仍然超过一半 选定一个候选主元素C，将一个数组分成两部分，前半部分有2k个（偶数个），后半部分有m个。 如果C在前半部分出现了k次，舍弃整个前半部分，并将下一个值赋给C,最后返回的结果是最有可能是主元素的数字（不一定是，还需要最后遍历判断） 比如【3，3，3，2，1，6，3，3，3，2，1】 我们舍弃【3，3，3，2，1，6】，3在剩余部分占比仍然超过一半，最后返回的是3， 比如【3，3，3，4，4，4，5，5，5，6，6】 这个集合没有主元素，返回结果是5，程序的最后遍历数组，得出5的次数，返回-1 再比如更一般的情况【3，4，5，3，4，3，2，3，3】 第一步舍弃【3，4】，第二步舍弃【5，3】，第三部舍弃【3，2】，返回结果3

public static int mainElement(int[]num,int n){        int seed = num[0];        int count = 1;        int i = 0;        //取出主元素        for(i = 1; i
   
    0){                    count--;                }else{                    seed = num[i];                }            }        }        //判断取出的主元素是不是主元素        count = 0;        for(i = 0;i
    
     = n/2){            return seed;        }        return 0;    }}
    
   

转载地址：http://crqen.baihongyu.com/