首页 > 代码库 > 在一个整型数组中有一个元素的出现次数超过了数组长度的一半，试设计一个 在时间上尽可能高效的算法，找出这个元素。
在一个整型数组中有一个元素的出现次数超过了数组长度的一半，试设计一个 在时间上尽可能高效的算法，找出这个元素。
题目：在一个整型数组中有一个元素的出现次数超过了数组长度的一半，试设计一个 在时间上尽可能高效的算法，找出这个元素。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
（1）基本的设计思想：一个数字出现的次数超过了长度的一半， 那么我们可以这样认为这个数字出现的个数一定大于其他全部数字出现的个数之和。算法的步骤如下：①设数组为data[]，数组长度为n，i=1。置currentAxis=data[0]，currentNum=1。②当data[i]==currentAxis时，currentNum++，转向④；否则转向③。③currentNum--，当currentNum==0时，currentAxis=data[i]。④当i==data.length时， 转向⑤；否则，i++，转向②；⑤返回currentAxis。（2）算法实现：
#include<iostream>using namespace std;int funtion(int data[],int length){ int currentAxis; //假设要求的元素的位置 int currentNum = 0; //要求元素的个数变量 for(int i =0;i<length;i++) { if(currentNum ==0){ //如果要求的元素还没出现，设置要求的元素为现在要比较的元素 currentAxis=data[i]; currentNum=1; } else { if(currentAxis==data[i]) //假设的结果与比较元素不同，假设结果个数增1，否则减1 currentNum++; else currentNum--; } } return currentAxis; //返回最终结果的位置。}int main(){ int arr[]={1,2,3,2,5,6,2,2,3,2,2,4}; cout<<"number="<<funtion(arr,12)<<endl; return 0;}
（3）时间复杂度为O(n)。空间复杂度O(1)。
【另解】本题最直接的方法就是对每个数字进行排序。然后输出出现次数最大的数字即可，但排序的时间复杂度最快也要O(nlog2n)。
在一个整型数组中有一个元素的出现次数超过了数组长度的一半，试设计一个 在时间上尽可能高效的算法，找出这个元素。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。