Majority Element

描述

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.

分析

这题最简单的解法，先把数组排序，O(nlogn)，然后从头到尾扫描一遍，找出最长的连续子串。

由于超过⌊ n/2 ⌋次，可以对上面的方法改进一下，排序后，不需要扫描，直接返回中间那个元素，nums[n/2]，肯定就是答案。

上述两个方法都是 O(nlogn)的，本题有一个线性解法。由于超过⌊ n/2 ⌋，可以用相抵消的思想，凡是和最多元素不相等的，就抵消，最后剩下的一定就是最多的那个元素。

解法1 排序

  1. // Majority Element
  2. // Time Complexity: O(nlogn), Space Complexity: O(1)
  3. public class Solution {
  4.     public int majorityElement(int[] nums) {
  5.         Arrays.sort(nums);
  6.         return nums[nums.length/2];
  7.     }
  8. }

解法2 线性解法

  1. // Majority Element
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public int majorityElement(int[] nums) {
  5.         int result = 0;
  6.         int count = 0;
  8.         for (int x : nums) {
  9.             if (count == 0) {
  10.                 result = x;
  11.                 count = 1;
  12.             } else if (result == x) {
  13.                 ++count;
  14.             } else {
  15.                 --count;
  16.             }
  17.         }
  18.         return result;
  19.     }
  20. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/majority-element.html