支配点

import java.util.Arrays;

/**
 * 支配点问题： 支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a =
 * {3,3,1,2,3};3为支配数，0，1，4分别为支配点； 要求：返回任何一个支配点
 * 
 * @author fangtengfei
 * @date 2010-5-15
 */
public class ControlPoint {

 public static void main(String[] args) {
  int[] a1 = { 3, 3, 1, 2, 3, 3, 1, 3, 4 };
  int[] a2 = { 1, 1, 1, 2, 3, 3, 1, 3, 4 };
  int[] a3 = { 3, 1, 3, 1, 2, 3, 1, 1, 1 };
  System.out.println(getControlPoint(a1));
  System.out.println(getControlPoint(a3));
  System.out.println(getControlPoint(a2));
 }

 private static int getControlPoint(int[] a) {
  // 只有长度大于二的数组才可能有支配数
  if (a == null || a.length < 2) {
   return -1;
  }
  // 先排序，找出中位数，如果存在支配数，必是中位数
  int[] b = a;
  Arrays.sort(b);
  int median = b[b.length / 2];
  int controlPointIndex = -1;
  int controlPointLength = 0;
  // 中位数
  for (int j = 0; j < a.length; j++) {
   int k = a[j];
   if (median == k) {
    controlPointIndex = j;
    controlPointLength++;
   }
  }
  if (controlPointLength > a.length / 2) {
   return controlPointIndex;
  }
  return -1;
 }
}