(剑指Offer)面试题29:数组中出现次数超过一半的数字
2023-09-14 08:59:06 时间
题目:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。
思路:
1、方法1:
先排序,然后找中位数;
时间复杂度O(nlogn)
2、方法2:
基于Partition函数的O(n)算法,即寻找第k(k=n/2)大的数;
平均时间复杂度:O(n)
3、方法3:
根据数组特点,采用Moore-Vote方法。
由于该数字的出现次数比所有其他数字出现次数的和还要多,因此可以考虑在遍历数组时保存两个值:一个是数组中的一个数字,一个是次数,。当遍历到下一个数字时,如果下一个数字与之前保存的数字相同,则次数加1,如果不同,则次数减1,如果次数为0,则需要保存下一个数字,并把次数设定为1。由于我们要找的数字出现的次数比其他所有数字的出现次数之和还要大,则要找的数字肯定是组后一次把次数设为1时对应的数字。
时间复杂度为O(n),空间复杂度为O(1)。
代码:
方法2:
#include <iostream> using namespace std; bool g_bInputInvalid=false; bool CheckInvalidArray(int* numbers,int length){ if(numbers==NULL || length<=0) g_bInputInvalid=true; return g_bInputInvalid; } bool CheckMoreThanHalf(int* numbers,int length,int number){ int times=0; for(int i=0;i<length;i++){ if(numbers[i]==number) times++; } bool isMoreThanHalf=true; if(times*2<=length){ g_bInputInvalid=true; isMoreThanHalf=false; } return isMoreThanHalf; } int Partition(int* numbers,int start,int end){ int key=numbers[start]; int i=start; int j=end; while(i<j){ while(i<j && numbers[j]>=key) --j; if(i<j) numbers[i++]=numbers[j]; while(i<j && numbers[i]<=key) ++i; if(i<j) numbers[j--]=numbers[i]; } numbers[i]=key; return i; } int MoreThanHalfNum(int* numbers,int length){ if(CheckInvalidArray(numbers,length)) return 0; int mid=length>>1; int start=0; int end=length-1; int index=Partition(numbers,start,end); while(index!=mid){ if(index>mid){ end=index-1; index=Partition(numbers,start,end); } else{ start=index+1; index=Partition(numbers,start,end); } } int result=numbers[index]; if(!CheckMoreThanHalf(numbers,length,result)) result=0; return result; } int main() { int A[]={3,1,3,2,4,3,3,5,3,7,3}; int length=sizeof(A)/sizeof(A[0]); cout << MoreThanHalfNum(A,length) << endl; return 0; }
方法3:
#include <iostream> using namespace std; bool g_bInputInvalid=false; bool CheckInvalidArray(int* numbers,int length){ if(numbers==NULL || length<=0) g_bInputInvalid=true; return g_bInputInvalid; } bool CheckMoreThanHalf(int* numbers,int length,int number){ int times=0; for(int i=0;i<length;i++){ if(numbers[i]==number) times++; } bool isMoreThanHalf=true; if(times*2<=length){ g_bInputInvalid=true; isMoreThanHalf=false; } return isMoreThanHalf; } int MoreThanHalfNum_1(int* numbers,int length){ if(CheckInvalidArray(numbers,length)) return 0; int result=numbers[0]; int times=1; for(int i=1;i<length;i++){ if(times==0){ result=numbers[i]; times=1; } if(result==numbers[i]) times++; else times--; } if(!CheckMoreThanHalf(numbers,length,result)) result=0; return result; } int main() { int A[]={3,1,3,2,4,3,3,5,3,7,3}; int length=sizeof(A)/sizeof(A[0]); cout << MoreThanHalfNum_1(A,length) << endl; return 0; }
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/e8a1b01a2df14cb2b228b30ee6a92163?rp=2
AC代码:
方法1:
class Solution { public: int Partition(vector<int> &numbers,int start,int end){ int key=numbers[start]; int i=start; int j=end; while(i<j){ while(i<j && numbers[j]>=key) --j; if(i<j) numbers[i++]=numbers[j]; while(i<j && numbers[i]<=key) ++i; if(i<j) numbers[j--]=numbers[i]; } numbers[i]=key; return i; } int MoreThanHalfNum_Solution(vector<int> numbers) { int length=numbers.size(); if(length<=0) return 0; int mid=length>>1; int start=0; int end=length-1; int index=Partition(numbers,start,end); while(index!=mid){ if(index>mid){ end=index-1; index=Partition(numbers,start,end); } else{ start=index+1; index=Partition(numbers,start,end); } } int result=numbers[index]; int times=0; for(int i=0;i<length;i++){ if(numbers[i]==result) times++; } if(times*2<=length) result=0; return result; } };
方法2:
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int length=numbers.size(); if(length<=0) return 0; int result=numbers[0]; int times=1; for(int i=1;i<length;i++){ if(times==0){ result=numbers[i]; times=1; } if(result==numbers[i]) times++; else times--; } int t=0; for(int i=0;i<length;i++){ if(numbers[i]==result) t++; } if(t*2<=length) result=0; return result; } };
相关文章
- 最新最全的Java面试题整理(内附答案)
- redis面试题
- (剑指Offer)面试题51:数组中重复的数字
- (剑指Offer)面试题40:数组中只出现一次的数字
- (剑指Offer)面试题38:数字在排序数组中出现的次数
- (剑指Offer)面试题14:调整数组顺序使奇数位于偶数前面
- (剑指Offer)面试题8:旋转数组的最小数字
- (剑指Offer)面试题40:数组中只出现一次的数字
- (剑指Offer)面试题14:调整数组顺序使奇数位于偶数前面
- (剑指Offer)面试题8:旋转数组的最小数字
- 回顾面试题:计算两个数组交集
- vue面试题:说说vue操作真实dom性能瓶颈
- PHP面试题:你所知道的php数组相关的函数?
- PHP面试题:合并两个数组有几种方式,试比较它们的异同
- PHP面试题:请写一段程序,在服务器创建一个文件fruit.dat,将试题3中得到的数组写入到改文件中,然后写一段程序从文件中读取并还原数组@author zhuwenqiong
- Java面试题 Java如何进行高效的数组拷贝?【Arrays.copyOf()】
- 【LeetCode 中等 矩阵】面试题 01.08 零矩阵
- 面试题 08.07. 无重复字符串的排列组合-dfs法
- 面试题 01.04. 回文排列-辅助数组法
- 面试题 ——— 二维数组的查找
- 微软面试题之两个链表的第一个公共结点
- 微软面试题:鸡蛋从第N层及以上的楼层落下会摔破
- 字节、百度、美团、腾讯技术面,面试题及答案分享(Android岗)
- MySQL常见面试题与答案