169. Majority Element

    xiaoxiao2021-03-25  59

    Given an array of size n, findthe majority element. The majority element is the element that appears morethan n/2 times.

    You may assume that the arrayis non-empty and the majority element always exist in the array.

        翻译:给定一个大小为n的数组,找到多数元素。多数元素是出现超过n / 2倍的元素。您可以假定数组非空,并且多数元素始终存在于数组中。

        第一想法是排序取nums.length的一半,但是总是超时,用冒泡和快速排序。最后用了常规的遍历,写完后,看了下别人的,发现直接用Arrays的静态方法排序成功了,看了一下,它是用“经过调优的快速排序法”,代码如下:

    public intmajorityElement(int[] nums) {

           /* int max=nums[0];

            int count=1;

            for(int i=1;i<nums.length;i++){

                if(count==0){

                    max=nums[i];

                    count++;

                }else{

                    if(count>nums.length/2)break;

                    if(nums[i]==max){

                        count++;

                    }else{

                        count--;

                    }

                   

                }

            }

            return max;*/

             Arrays.sort(nums);

            return nums[nums.length/2];

           

        }

    转载请注明原文地址: https://ju.6miu.com/read-50203.html

    最新回复(0)