【面试题】剑指Offer-29-找到出现次数超过一半的数字

    xiaoxiao2021-03-26  3

    题目概述

    解题思路

    方法1

    进行排序,排序后,超过一半次数的数字一定会出现数组的最中间的位置上

    方法2

    利用快排的思想,单次排序,会将数组分成两个区间

    通过判断所分区间的中间元素是否为数组的中间值

    来进行逐次划分求解

    这里和快排很相似,就没有实现

    时间复杂度为O(N)

    方法3

    巧妙思路

    用两个变量,一个保存当前记录的数字,一个保存次数(初始化为0)

    遍历一遍数组

    如果数字与当前数保持相同,则次数加1

    否则,次数减1

    若次数减为0,则保存下一个位置的数字

    时间复杂度O(N)

    代码实现

    方法1

    //方法1:排序后取中间值 //直接插入排序的思想 //分成两个数组 //第一个数组是有序的,第二个是无序的 //开始的时候,只有第一个数在第一个数组 //升序 void InsertSort(int* arr, size_t n) { for (int i = 1; i < n; ++i) { int j = i - 1; int tmp = arr[i]; for (; j >= 0; --j) { //如果tmp比该位置大 if (tmp > arr[j]) break; arr[j + 1] = arr[j]; } arr[j+1] = tmp; } } int MoreThanHalf1(int* arr, size_t n) { InsertSort(arr, n); int midIndex = n >> 1; return arr[midIndex]; } 该算法的时间复杂度为O(N^2)

    可以用其他排序,最快为O(N*logN)

    方法3

    //方法3 //用快排,找中间的数 //方法3 //用技巧 pair<bool,int> MoreThanHalf3(int* arr, size_t n) { int num = arr[0]; int count = 1; for (size_t i = 1; i < n; ++i) { if (num == arr[i]) count++; else count--; if (count == 0) { if (i >= n - 1) return make_pair(false,0); num = arr[i + 1]; } } return make_pair(true, num); } 方法3中,注意判断传入数组有误的情况

    用pair结构体,第一个元素表示数组是否符合题目要求

    第二个元素表示最后返回的超过一半的数字

    当然,如果第一个元素为FALSE,则第二个元素就不用关心了

    转载请注明原文地址: https://ju.6miu.com/read-500111.html

    最新回复(0)