leetcode 169 Majority Element

tangr206 發(fā)布于2019-08-15 13:53 / 2873人閱讀

摘要：因?yàn)楸姅?shù)出現(xiàn)的次數(shù)必定大于，所以我們只要取第個(gè)位置上的元素，這個(gè)元素一定為我們要找的眾數(shù)。

題目詳情

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.You may assume that the array is non-empty and the majority element always exist in the array.輸入一個(gè)大小為n的數(shù)組，整個(gè)數(shù)組里面將會(huì)含有一個(gè)眾數(shù)，即這個(gè)元素出現(xiàn)的次數(shù)大于n/2，我們需要找到并返回這個(gè)眾數(shù)

思路

這道題也是一道關(guān)于數(shù)組的重復(fù)元素的問(wèn)題

首先我想到的辦法是，使用HashMap實(shí)現(xiàn)，key是元素的值，value則是這個(gè)元素在當(dāng)前出現(xiàn)的次數(shù)，一旦這個(gè)次數(shù)大于n/2，我們就可以停止我們的遍歷

但實(shí)際上，還有一種更簡(jiǎn)單的方法。因?yàn)楸姅?shù)出現(xiàn)的次數(shù)必定大于n／2，所以我們只要取第n/2個(gè)位置上的元素，這個(gè)元素一定為我們要找的眾數(shù)。

感謝@SegmentWarrior提供的解法三，不需要建立hashmap所產(chǎn)生的額外空間，同時(shí)時(shí)間復(fù)雜度為O(n)

解法一 HashMap

    //HashMap實(shí)現(xiàn) 時(shí)間復(fù)雜度O(n)
    public int majorityElement(int[] nums) {
        HashMap count = new HashMap();
        int length = nums.length;
        if(length<=1){
            return nums[0];
        }
        for(int i=0;i length/2){
                    return nums[i];
                }
            }else{
                count.put(nums[i], 1);
            }

        }
        
        return -1;
    }

解法二直接取n/2位置元素

    //思想：對(duì)于一個(gè)排序好的數(shù)組，第n/2的位置的元素一定是存在的這個(gè)眾數(shù)
    public int majorityElement(int[] nums) {
        
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

解法三對(duì)出現(xiàn)次數(shù)計(jì)數(shù)

    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        
        for(int i=1;i1) count --;
            else res = nums[i];
        }
        return res;
    }