169. 多数元素

题目：

169. 多数元素
面试题39. 数组中出现次数超过一半的数字
在这里插入图片描述

题解：

1. 最原始的思路：

先排序，然后遍历整个数组，对记录每个数值出现的次数进行统计即可。

2. 排序法：

在这里插入图片描述

3. 摩尔投票法：（首选）

在这里插入图片描述

代码：

1. 最原始的思路：

/** * code169 */
import java.util.*;
public class code169 { 
    public static int majorityElement(int[] nums) { 
        if (nums.length == 1) { 
            return nums[0];
        }
        Arrays.sort(nums);
        int count = 1;
        int res = -1;
        for (int i = 0; i < nums.length - 1; i++) { 
            if (nums[i] == nums[i + 1]) { 
                count++;
            } else { 
                count = 1;
            }
            if (count > (nums.length - 1) / 2) { 
                res = nums[i];
            }
        }
        return res;
    }
    public static void main(String[] args) { 
        int nums1[] = {  3, 2, 3 };
        int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
        int ans1 = majorityElement(nums1);
        int ans2 = majorityElement(nums2);
        System.out.println(ans1 + " " + ans2);
    }
}

2. 排序法：

/** * code169 */
import java.util.*;
public class code169 { 
    public static int majorityElement(int[] nums) { 
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    public static void main(String[] args) { 
        int nums1[] = {  3, 2, 3 };
        int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
        int ans1 = majorityElement(nums1);
        int ans2 = majorityElement(nums2);
        System.out.println(ans1 + " " + ans2);
    }
}

3. 摩尔投票法：（首选）

/** * code169 */
import java.util.*;
public class code169 { 
    // 摩尔投票法：
    public static int majorityElement(int[] nums) { 
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) { 
            if (candidate == nums[i]) { 
                count++;
            } else { 
                count--;
            }
            if (count == 0) { 
                candidate = nums[i];
                count = 1;
            }
        }
        return candidate;
    }
    public static void main(String[] args) { 
        int nums1[] = {  3, 2, 3 };
        int nums2[] = {  2, 2, 1, 1, 1, 2, 2 };
        int ans1 = majorityElement(nums1);
        int ans2 = majorityElement(nums2);
        System.out.println(ans1 + " " + ans2);
    }
}