今天看到一个很有意思的面试题，大致是：找出一个数组中，某元素出现次数超过元素长度一半的元素。这题目的重点是：采用高效的算法。
查了一圈资料，发现一个思路比较好。那就是：我们先假设这个元素存在，那么这个元素出现的次数一定比其他元素出现次数的和都要多。我们先假设第一个元素就是我们要找的元素num = arr[0]，并定义一个计数器count，如果与下一个元素相同，count++；如果不同，count--。当count==0时，那么num=arr[i]，count=1，继续下去。那么最后一次计数器count置为1时，这个元素arr[i]就是我们要找的元素了。
代码如下：
/** * */ public class GetNum { public static void main(String[] args) { int arr1[] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 }; int result1 = getNum(arr1); System.out.println(result1); int arr2[] = { 2, 2, 2, 2, 2, 1, 3, 4, 5 }; int result2 = getNum(arr2); System.out.println(result2); } private static int getNum(int[] arr) { if (arr == null && arr.length < 1) { return -1; } int num = arr[0]; int count = 1; // 遍历比较 for (int i = 1; i < arr.length; i++) { if (num == arr[i]) { ++count; } else { count--; if (count == 0) { num = arr[i]; count = 1; } } } // 验证num是不是目标数字，有可能并不存在这样的元素 count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == num) { count++; } } if (count >= arr.length / 2) { return num; } return -1; } }参考资料：https://blog.csdn.net/nwpu_geeker/article/details/79699348
