题目1
给定一个整型数组arr, 打印其中出现次数大于一半的数， 如果没有这样的数，打印提示信息
进阶
给定一个整型数组arr, 再给定一个整数K， 打印所有出现次数大于 N/K的数，如果没有这样的数字，打印提示信息
题目的思路是：
一般都思路是 哈希表记录每个数跟出现的次数，但是额外空间复杂度是O（N）
现在提供一个方法，核心思想是：
一次在数组中删掉K个不同的数，不停的删除，知道剩下的数种类不足K就停止删除， 那么，如果在数组中出现的次数大于 N/K, 则这个数最后一定会被剩下
说白了就是：数组，与次数有关的 可以使用删除法 。 类似于 拿着相同的数去干掉不同的，剩下的就是阵容强大的那一组。
在删除时候使用的策略是，记录当前位置的数，遍历下一个，如果不一致那就可以ko掉一个。
题目1 ： 每次一次在数组中删掉两个不同的数，不停的删除，直到剩下的数只有一种。 一个干一个，一个干掉一个（逻辑干掉，time的减少。当前的和下一个去抵消，最后看看剩下个啥子）
package TT;
public class Test66 {
public static void printHalfMajor(int[] arr){
int cand = 0;
int times = 0;
for(int i = 0; i!=arr.length; i++){
if(times ==0){
cand = arr[i];
times = 1;
}else if(arr[i]== cand){
times++;
}else{
times--;
}
}
times = 0;
for(int i =0; i!=arr.length; i++){
if(arr[i] == cand){
times++;
}
}
if(times > arr.length/2){
System.out.println(cand);
}else {
System.out.println("no such number");
}
}
public static void main(String[] args){
int[] arr = new int[6];
arr[0]=2;
arr[1]=1;
arr[2]=2;
arr[3]=4;
arr[4]=2;
arr[5]=2;
printHalfMajor(arr);
}
}我再用比较繁琐一些，容易理解上一些。核心的思想： 拿出record去一直做pk，一直pk的条件是times这个能量值不为0。
如果record为0，那么下台，换一个，从新去跟后面pk。
public class Test8 {
public static Integer getNumOverHalf(int[] arr){
if (arr.length<=2 && arr.length%2 !=0){
throw new RuntimeException("长度不够！") ;
}
int times = 0 ; //剩下的数量
int record= 0;
for (int i=0; i<arr.length; i++){
if (times==0){ //如果剩余量为0 那么记录下当前的 然后继续加
record=arr[i];
times = 1;
} else if (arr[i]!= record){
times--;
}else if (arr[i]==record){
times++;
}
}
times=0;
for (int i=0; i<arr.length; i++){
if (arr[i]==record){
times++;
}
}
if (times == (arr.length/2)){
return record;
}else {
System.out.println("没有！");
return null;
}
}
public static void main(String[] args) {
int[] arr = {1,2,4,3,4,4};
System.out.println(getNumOverHalf(arr));
}
}数组，与次数有关的 可以使用删除法 。 类似于 拿着相同的数(record下来的)去干掉不同的，剩下的(record下来的)就是阵容强大。 然后统计下留下的这个(占有量做多的)，再去遍历数组进行检验。就OK了