力扣算法题-面试题17.10-多数元素-java代码

数组中占比超过一半的元素称之为主要元素。给定一个整数数组,找到它的主要元素。若没有,返回-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)
思路一:基本思想:摩尔投票算法:
以 [2,2,1,3,1,2,2] 为例。
遍历数组第一个元素 2 时,因 major 空缺,所以赋值 major = 2,且票数 count = 1()

力扣算法题-面试题17.10-多数元素-java代码
如果数组中存在最多元素,最终得到的major即为主要元素;
如果数组中不存在;最终得到的major则不是主要元素;例如:3,3,3,2,2,2,1;最终major为1则不是主要元素,应该返回-1
所以最后需要再次进行判断,查看该major在数组中的数量是否为数组长度的一半以上
代码:

public int majorityElement(int[] nums) {
        int major = 0;
        int count = 0;
        int length2 = nums.length/2+1;//该length代表数组长度一半
        //摩尔算法实现
        for(int i = 0;i<nums.length;i++)
        {
            if(count == 0)
            {
                major = nums[i];
                count++;
            }else{
                if(major == nums[i])
                {
                    count ++;
                }else{
                    count--;
                }
            }
        }
        //检验major在数组中的数量count2
        int count2 = 0;
        for(int i = 0;i < nums.length;i++)
        {
            if(nums[i] == major)
            {
                count2++;
            }
        }
        return (count2 >= length2)?major:-1;//验证major的数量是否超过数组长度一半
    }

思路二、先对目标数组进行排序,这样相同的元素肯定是排在一起的,然后记录count;如果的到count超过数组长度的一半,则返回对应元素,否则返回-1;
但是该方法由于需要排序,所有时间复杂度至少为O(NlogN),不符合题目要求,仅供参考
操作:Array().sort(目标数组):对目标数组进行排序
代码:

 public int majorityElement(int[] nums) {
        Arrays.sort(nums);//调用arrays中的sort方法。时间复杂度O(NlogN,不符合要求)
        int count = 0;//记录元素的数量
        int major= -1;//记录当前元素
        if(nums.length == 1)
        {
            return nums[0];
        }
        for(int i = 0;i<nums.length;i++)
        {
           if(major == -1)
           {
               major = nums[i];
               count ++;
           }else
           {
               if(nums[i] == major)
               {
                   count ++;
                   if(count >= nums.length/2+1)
                   {
                       return major;
                   }
               }else{
                   count = 1;
                   major = nums[i];
               }
           }
        }    
        return -1;
    }
上一篇:外设驱动程序设计


下一篇:javascript数据类型之字符串