給定一個(gè)大小為 n 的數(shù)組，找到其中的眾數(shù)。眾數(shù)是指在數(shù)組中出現(xiàn)次數(shù)大于?? n/2 ??的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在眾數(shù)。

示例?1:

輸入: [3,2,3]
輸出: 3
示例?2:

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

排序之后遍歷一次即可

import java.util.Arrays;

public class Solutino169 {
?? ?public static int majorityElement(int[] nums) {
?? ??? ?int n = nums.length;
?? ??? ?int i,sum=1;
?? ??? ?Arrays.sort(nums, 0, nums.length);
?? ??? ?for(i=0;i<n-1;i++)
?? ??? ?{
?? ??? ??? ?if(nums[i]==nums[i+1])
?? ??? ??? ?{
?? ??? ??? ??? ?sum++;
?? ??? ??? ??? ?if(sum>n/2)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?return nums[i];
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?sum = 1;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return nums[0];
? ? ? ??
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?//int[] nums = {3,2,3};
?? ??? ?int[] nums = {2,2,1,1,1,2,2};
?? ??? ?System.out.println(majorityElement(nums));
?? ?}
}
?

針對(duì)上面的代碼，可以有一個(gè)改進(jìn)，不論眾數(shù)是數(shù)組中的最大，最小值，或者是中間值

因?yàn)樗臄?shù)量大于總數(shù)的一半，因此排序完成后的n/2位置處一定是眾數(shù)

import java.util.Arrays;

public class Solutino169 {
?? ?public static int majorityElement(int[] nums) {
?? ??? ?Arrays.sort(nums, 0, nums.length);? //兩行代碼即可完成
?? ??? ?return nums[nums.length/2];
? ? ? ??
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?//int[] nums = {3,2,3};
?? ??? ?int[] nums = {2,2,1,1,1,2,2};
?? ??? ?System.out.println(majorityElement(nums));
?? ?}
}
?

總結(jié)

以上是生活随笔為你收集整理的Leetcode--169. 求众数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。