《剑指offer第二版》面试题39：数组中出现次数超过一半的数字

题目描述

• 数组中有一个数字出现次数超过数组长度的一半，请找出这个数字，也称为中位数。比如数组为{1, 2, 3, 2, 2, 2, 5, 4, 2}，则输出2。

解体思路1：

• 1. 如果对这个数组排序，则数组中间的数字肯定是出现次数超过数组长度的一半的数字。
• 2. 先在数组中随机选取一个数字，然后调整数字的顺序，比这个数大的在右边，比这个数小的在左边。
• 3. 如果这个选择的数字下标刚好是数组长度的一半，则这个数字就是中位数。
• 4. 如果这个选择的数字下表小于数组长度的一半，则中位数位于这个数的右边。在这个数字的右边继续查找。
• 5. 如果这个选择的数字下表大于数组长度的一半，则中位数位于这个数的左边。在这个数字的左边继续查找。
• 6. 可以借助快速排序的方法进行查找。

代码

int moreThanHalfNum(int[] arrs) {
     if (arrs == null || arrs.length <= 0) {
         return 0;
     }
     int start = 0;
     int end = arrs.length - 1;
     int middleIndex = partation(arrs, start, end);
     while (middleIndex != arrs.length / 2) {
         if (middleIndex < arrs.length / 2) {
              // 中位数位于middleIndex的右边
             start = middleIndex + 1;
             middleIndex = partation(arrs, start, end);
         } else {
             // 中位数位于middleIndex的左边
             end = middleIndex - 1;
             middleIndex = partation(arrs, start, end);
         }
     }
     // 检查查找到的数字出现的次数是否大于数组长度的一半，不满足说明数组中不存在次数超过数组长度的一半的数字。
     if (!checkMoreThanHalf(arrs, arrs[middleIndex])) {
         return 0;
     }
     return arrs[middleIndex];
 }


 int partation(int[] arrs, int start, int end){
     int pivot = arrs[start];
     while (start < end) {
         while (arrs[end] >= pivot && end > start) {
             end--;
         }
         if (start < end) {
             arrs[start] = arrs[end];
             start++;
         }

         while (arrs[start] < pivot && start < end) {
             start++;
         }
         if (end > start) {
             arrs[end] = arrs[start];
             end--;
         }
     }
     arrs[end] = pivot;
     return end;
 }

 boolean checkMoreThanHalf(int[] arrs, int value){
     int times = 0;
     for (int i = 0; i < arrs.length; i++) {
         if (arrs[i] == value) {
             times ++;
         }
     }
     return times * 2 > arrs.length;
 }

解体思路2：

• 1. 如果一个数字出现次数超过数组长度的一半，则它出现的次数比其他所有数字出现次数的总和还要多。
• 2. 可以对数组进行遍历，保存数组中的一个数字，以及出现的次数。如果当前数字和之前保存的数字一样，则次数增加，不一样则次数递减。当次数为0，则保存的数字变为当前数字，次数为1。
• 3. 找的数字肯定是最后一次把次数设置为1的数字。

代码

int moreThanHalfNum_v2(int[] arrs) {
    if (arrs == null || arrs.length <= 0) {
        return 0;
    }
    int times = 1;
    int value = arrs[0];
    for (int i = 1; i < arrs.length; i++) {
        if (arrs[i] != value) {
            times --;
        } else {
            times ++;
        }
        if (times == 0) {
            value = arrs[i];
            times = 1;
        }
    }
    if (!checkMoreThanHalf(arrs, value)) {
        return 0;
    }
    return value;
}