剑指offer—数组中出现超过一半的数 解答

剑指offer—数组中出现超过一半的数

题目描述

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

思路—滑动窗口

  • 一开始想法是使用数组,把每个值的存放到它值对应下表,出现一次,下标+1,但是可能出现负数,数组放不了,于是这种想法不了了之
  • 于是想法还是回到了万能的排序上,排序后对数组进行处理,拿到众数,因为排完序众数肯定是出现在一起的,这个时候想到了滑动窗口,用一个长度为数组一半的滑动窗口,只要滑动窗口中第一个值和最后一个值相等,那么其中间的数肯定相等,说明该数为众数

代码

class Solution {
    public int majorityElement(int[] a) {
        Arrays.sort(a);
        int size = a.length/2 +1;
        for(int m=0;m<=a.length-size;m++){
            if(a[m]==a[m+size-1]){
                return a[m];
            }
        }
        return 0;
    }
}
class Solution {
    public int majorityElement(int[] a) {
        if(a.length==1) return a[0];
        Arrays.sort(a);
        int i = 0;
        int size = a.length/2 +1;
        while(i<=a.length-size){
            for(int m=i;m<i+size;m++){
                if(m==i) continue;
                if(m==i+size-1){
                    if(a[m]==a[m-1]){
                        return a[m];    
                    }else {i++;break;}
                }
            }
        }
        return 0;
    }
}