2019-05-23排序案例1

package 排序案例;

public class ExceedHalf { // 在一个数组中有一个数的数量是超过这个数组长度一半的请你找出这个数
    // 因为这个数组的个数超过了数组长度的一半所以可以我们parpation一下数组然后中间的那个元素就是结果了
    public static int exceed(int[] arr) {
        int num = arr[0];
        int time = 1;
        for(int i = 1; i < arr.length; i++) {
            if(num == arr[i] ) {
                time++;
            }else if(time == 0){   // num != arr[i] && time == 1这种写法只能用于超过一半的数刚好等于一半的就没有办法解决
                                  // 说的不好听的就是没有把握关键变量
                num = arr[i];
                time = 1;
            }else {
                time--;
            }
        }
        return num; 
        // 第二种方法消除法num候选值time这个值出现的次数扫描数组如果前后两个值相同time+1如果不同time就-1当time=0时num就换成下一个值
        //return partation(arr, 0, arr.length - 1);
    }
    public static int partation(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r + 1;
        int num = arr[r];
        while(l < more) {
            if(arr[l] < num) {
                swap(arr, l++, ++less);
            }else if(arr[l] == num) {
                l++;
            }else {
                swap(arr, l, --more);
            }
        }
        return arr[arr.length / 2];
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 3, 3, 3};
        System.out.println(exceed(arr));
    }
    

}