Majority Number

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

基本上是一个抵消的思路, 同时遍历两个数, 如果两个数不同, 就都一起抛弃, 最后留下的数就是所求目标.

具体应用挺有意思的...
编程之美中的寻找发贴“水王”

public int findMajorityNumber(int[] nums) {
  int candidate = Integer.MIN_VALUE;
  int count;

  for (int i = count = 0; i < nums.length; i++) {
   if (count == 0) {
    candidate = nums[i];
    count = 1;
   } else {
    if (candidate == nums[i]) {
     count++;
    }  else {
     count--;
    }
   }
  
  }
  return candidate;
 }

然后还有个follow up 版本问题, 如果要找的数在数组中出现 n/3 次, 又如何找到?
本质上和找水王相同, 就是从两个数不同抛弃变成三个数不同才抛弃, 只需要多加一个candidate来维护就行.

public int findMajorityNumberII(int[] nums) {
  int candidateA = Integer.MIN_VALUE, candidateB = Integer.MIN_VALUE;
  int countA = 0, countB = 0;
  for (int i = 0; i < nums.length; i++) {
   if (countA == 0) {
    if (nums[i] == candidateB) {
     countB++;
    } else {
     candidateA = nums[i];
     countA++;
    }
   } else if (countB == 0) {
    if (nums[i] == candidateA) {
     countA++;
    } else {
     candidateB = nums[i];
     countB++;
    }
   } else {
    if (nums[i] == candidateA) {
     countA++;
    } else if (nums[i] == candidateB) {
     countB++;
    } else {
     countA--;
     countB--;
    }
   }
  }
  
  if (countA > 0) {
   return candidateA;
  } else {
   return candidateB;
  }

上述代码应该算是伪代码, 实际解决过程中应该还要对最后所得到的数count一次以保证正确性 参考: http://www.geeksforgeeks.org/majority-element/