题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
1. 基于快排 （会污染数组） 其实只要涉及顺序的问题，大多数都可以排序。这题可以建立在快排的基础上，每做一次划分之后，把当前划分元素的索引index返回，这个数就是整个数组第index小的数，如果index=len/2, 结束递归。因为出现次数超过数组长度一半的元素最后一定有一个在索引是len/2的位置。
bool ansIsValid = true; // 全局变量，=true时返回的0代表没有找到 bool isValid(int *nums, int len){ // 输入鲁棒性检查 if (nums == NULL || len < 1) return false; return true; } bool isMoreHalf(int *nums, int len, int num){ //看最后找到的元素的个数是否真的超过一半 int count = 0; for (int i = 0; i < len; ++i) { if (nums[i] == num) ++count; } if (count <= len / 2) return false; // 必须 > len / 2 才行！！ return true; } int Partition(int *nums, int start, int end) { //快排的一次划分，返回固定元素后的索引 int flag = nums[start]; int i = start, j = end; while (i < j) { while (i < j && nums[j] >= flag) --j; int rightmin = nums[j]; while (i < j && nums[i] <= flag) ++i; nums[j] = nums[i]; nums[i] = rightmin; } nums[start] = nums[i]; nums[i] = flag; return i; // i的位置不会变了 } int findCore(int *nums,int len) { // 主调函数 ansIsValid = true; // 默认答案无效，不仅下面鲁棒性要用，最后检验也要用 if (!isValid(nums, len)) { // 鲁棒性 return 0; } int mid = len >> 1; // 中位数索引 int start = 0; int end = len - 1; int index = Partition(nums, start, end); // 第一次划分 /* 为什么比的是索引而不是值，因为index前后一边大一边小是确定的 只有index到中间时，才能保证从头到中间，或者从中间到尾巴都是一个数 这样才能找到超过一半的数 */ while (index != mid) { // 出口 if (index > mid) end = index - 1; else start = index + 1; index = Partition(nums, start, end); // 选择左还是右划分 } if (isMoreHalf(nums, len, nums[index])) { // 检验是不是真的个数超过数组长度一半 ansIsValid = false; // 确实超过 return nums[index]; } else { return 0; } }方法2： 比较个数差 （没有污染数组）
从个数入手，有一个数字出现次数超过一半，也就是说它比其他所有数字次数和都多。我们把这个数和其他数分成两组 “相对抗” , 用一个变量存数字res，另一个存次数count。遍历数组，当前数字和上一个相等，次数+1；不等，次数-1，如果次数减到0，把res更新为当前数字，count更新为1. 到最后因为我们要找的数次数比其他的和都多，那么它一定时最后一次把count设成1的数。
bool isAns = true; // 判断return 0 时是不是有效 int findSBNumber(int nums[], int len) { isAns = true; // 要在鲁棒性检查之前设置 if (nums == NULL || len < 1) return 0; int ans = nums[0]; // 上文中的res int count = 1; for (int i = 0; i < len; ++i) { if (nums[i] != ans) { --count; if (count == 0) { count = 1; ans = nums[i]; } }else { ++count; } } count = 0; for (int i = 0; i < len; ++i) { // 验证是不是真的个数超过一半 if (nums[i] == ans) ++count; } if (count <= len / 2) return 0; isAns = false; return ans; }