//题目：输入一个数组，输出出现次数大于总次数一半的数字
//解法1：输出数字的出现次数大于整体的一半，所以可以出现数字标记+1，不同数字-1，为0时更新数字并使标记为1
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(getMaxNum(new int[]{2,2,2,3,3,3,2}));
}
public static int getMaxNum(int[] input){
int number = 0;
int count = 0;
for(int i = 0;i<input.length;i++){
if(count == 0){
number = input[i];
count = 1;
continue;
}
if(number == input[i]){
count++;
}else{
count--;
}
}
return number;
}
}
//解法2：使用快排思想，找到位置为mid的元素
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(getMaxNum(new int[]{2,2,3,3,3,3,2}));
}
public static int getMaxNum(int[] input){
int low = 0;
int high = input.length-1;
int mid = (low+high)/2;
int index = partition(input,low,high);
while(index!=mid){
if(index<mid){
index = partition(input,index+1,high);
}else{
index = partition(input,low,index-1);
}
}
return input[index];
}
public static int partition(int[] input,int low, int high){
int key = input[low];
while(low<high){
while(low<high && input[high]>=key){
high = high-1;
}
input[low] = input[high];
while(low<high && input[low]<=key){
low = low+1;
}
input[high] = input[low];
}
input[low] = key;
return low;
}
}
