数组和指针：超过一半的数字；水王发帖

二、超过一半的数字&＃xff1a;数组中有一个数字出现的次数超过了数组长度的一半&＃xff0c;找出这个数字

可以看出6出现的次数超过了数组长度的一半
数组长度为偶数
当出现次数最多的元素恰好全部排在左半区间时&＃xff0c;利用快速排序会很难判断

当出现次数较多的元素排列在正中间时&＃xff0c;可以利用快速排序&＃xff0c;可以返回数组5和6的下标

当出现次数较多的元素全部出现在右半区间时&＃xff0c;也很难判断
题目&＃xff1a;Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说&＃xff0c;Tango有一大“水王”&＃xff0c;他不但喜欢发帖&＃xff0c;还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子&＃xff08;包括回帖&＃xff09;的列表&＃xff0c;其中帖子作者的ID也在表中&＃xff0c;你能快速找出这个传说中的Tango水王吗&＃xff1f;

可以利用一遍扫描数组解决
水王占总数的一半&＃xff0c;说明总数必为偶数&＃xff1b;
假设隔一个数就是水王&＃xff0c;两两不同最后一定会消为0&＃xff1b;
水王也可能为最后一个元素&＃xff0c;每次扫描的时候&＃xff0c;多一个动作和最后一个元素作比较&＃xff0c;单独计数&＃xff0c;计数恰好等于一半&＃xff1b;计数不够一半&＃xff0c;那么去掉最后一个元素&＃xff0c;水王就是留下的那个candidate

两两不同&＃xff0c;最后消除后为0

package morethanhalf;
import java.util.Arrays;public class Solve {public static void solve4(int[] arr){ int candidate&＃61;arr[0]; //候选数int nTimes&＃61;0; //出现的次数int countOfLast&＃61;0; //统计最后这个元素出现的次数int N&＃61;arr.length;for(int i&＃61;0;i<N;i&＃43;&＃43;) {if(arr[i]&＃61;&＃61;arr[N-1]) //增加和最后一个元素比较的步骤countOfLast&＃43;&＃43;;if(nTimes&＃61;&＃61;0) {candidate&＃61;arr[i];nTimes&＃61;1;continue;}if(arr[i]&＃61;&＃61;candidate)nTimes&＃43;&＃43;;elsenTimes--;}if(countOfLast&＃61;&＃61;N/2) //最后一个元素出现的次数System.out.println(arr[N-1]);elseSystem.out.println(candidate);}
public static void main(String[] args) {solve4(new int[] {0,1,2,1,1});
}
}