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

子数组中最大出现次数最多的元素(Leedcode1157)

1.线段树(超时未通过,我不知道哪里有问题)

class MajorityChecker {    int[] arr;    int tree[];    public MajorityChecker(int[] arr) {        this.arr = arr;        this.tree = new int[100000];    }    public int query(int left, int right, int threshold) {        Map
   
     map =new HashMap<>();        update(0,left,right,arr[left]);        map.put(arr[left],1);        if(tree[0]>=threshold)        {            return  arr[left];        }        for(int i=left+1;i<=(left+right)/2;i++)        {             if(map.get(arr[i])==null)             {                 update(0,left,right,arr[i]);                 map.put(arr[i],1);                 if(tree[0]>=threshold)                     return arr[i];             }        }        return  -1;    }    //将树节点的值改为当前节点对应包含的值num出现的次数    public void update(int node,int left, int right,int num)    {        if(left==right)        {            if(arr[left]==num)                tree[node]=1;            else            {                tree[node]=0;            }        }        else        {            int left_node = node * 2 + 1;            int right_node = node * 2 + 2;            int middle = (left + right) / 2;            update(left_node, left, middle, num);            update(right_node, middle + 1, right, num);            tree[node] = tree[left_node] + tree[right_node];        }    }}
   

摩尔投票算法(复杂度很高但好理解，通过)

class MajorityChecker {
       int[] arr;    int num[];    public MajorityChecker(int[] arr) {
           this.arr = arr;    }    public int query(int left, int right, int threshold) {
           num = new int[20001];        int temp =  majorityNumber(arr,left,right,num);        int count = num[temp];        if(count>=threshold)            return temp;        else            return -1;    }    public int majorityNumber(int arr[], int left, int right,int num[])    {
           int temp = arr[left],count =0;        for(int i=left;i<=right;i++)        {
               if(count==0)            {
                   temp = arr[i];                count++;            }            else            {
                   if(arr[i]!=temp)                    count--;                else                    count++;            }        num[arr[i]]++;        }        return  temp;    }}

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