java怎么找到數(shù)組中的多數(shù)元素

這篇文章主要介紹“java怎么找到數(shù)組中的多數(shù)元素”，在日常操作中，相信很多人在java怎么找到數(shù)組中的多數(shù)元素問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”java怎么找到數(shù)組中的多數(shù)元素”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

問題：給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。比如：數(shù)組 [3，2，3] 的多數(shù)元素是 3 ，數(shù)組 [2，2，1，1，1，2，2] 的多數(shù)元素是 2 。

既然多數(shù)元素在數(shù)組中出現(xiàn)的次數(shù)大于 ? n/2 ? ，給這個(gè)數(shù)組排個(gè)序，然后取中間的值，得到的肯定就是多數(shù)元素，要不然不符合題意。

這樣的話，兩行代碼就可以搞定：

java Arrays.sort(nums); return nums[nums.length >> 1];

但是時(shí)間復(fù)雜度是 O(nlogn) ，空間復(fù)雜度是 O(logn) 。

咱們平時(shí)都是怎么投票的呢？大家每個(gè)人都選一個(gè)人寫在紙條上，然后開始拆開紙團(tuán)瞅瞅選的是誰(shuí)。剛開始默認(rèn)大家都是 0 票，然后紙條上投的是誰(shuí)，這個(gè)人就多一票，最后看誰(shuí)的票數(shù)比較多?；氐皆蹅冞@個(gè)題目，既然是眾數(shù)，而且出現(xiàn)的次數(shù)大于 ? n/2 ? ，那我們可以假設(shè)一個(gè)數(shù)就是要求的眾數(shù)，同時(shí)設(shè)置這個(gè)數(shù)字出現(xiàn)的次數(shù)為 0 ，然后和接下來(lái)的數(shù)字進(jìn)行比較。如果一樣呢，咱們把這個(gè)數(shù)字出現(xiàn)的次數(shù)加上 1 ，如果不一樣，就讓次數(shù)減 1 ，當(dāng)這個(gè)值減到 0 時(shí)，說(shuō)明剛開始假設(shè)的數(shù)字不是眾數(shù)，那就換當(dāng)前的這個(gè)數(shù)字，繼續(xù)循環(huán)。這樣最后這個(gè)數(shù)字出現(xiàn)的次數(shù)一定是大于等于 0 的，要不然就不符合 出現(xiàn)的次數(shù)大于 ? n/2 ? 這個(gè)題意了，最后的最后，將真正的眾數(shù)返回即可。

java // 設(shè)置初始票數(shù)為 0 int count = 0 ; // 先將要求的眾數(shù)定義為空 Integer majorityElement = null; // 循環(huán)數(shù)組 for(int num : nums){ // 當(dāng) count 為 0 時(shí),假設(shè)當(dāng)前的數(shù)為要求的眾數(shù) if (count == 0){ majorityElement = num; } // 當(dāng) num 等于假設(shè)的眾數(shù)時(shí), count 就加 1 count += ( num == majorityElement ) ? 1 : -1 ; } // 最后返回真正的眾數(shù) return majorityElement;

到此，關(guān)于“java怎么找到數(shù)組中的多數(shù)元素”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！