数组之找出Array中出现次数超过一半的数

/*********数组之找出Array中出现次数超过一般的数，假设数组乱序；***********/ /***************************************************************************************************************************************************************/ //方法一：利用hash表；数组无需排序;建立一个Hash_map;其中key为数组元素的值，value为次数出现的次数； // 遍历一遍数组，用hash_map统计每个数出现的次数，并用两个值存储目前出现次数最多的数及对应的次数； // 时间复杂为O(n)，空间复杂度为O(n)； //关联性容容器map的特性之一：所有元素会根据元素的键值自动被排序；map不允许两个元素拥有相同的键值； //此方法同上题《找出数组中重复次数最多的数》 #include<iostream> #include<vector> #include<map> using namespace std; int findMoreThanHalfNum(vector<int> &nums) { map<int,int> maping; int len=nums.size(); int mostCount=1; int mostNum=nums[0]; for(int i=0;i<len;i++) { maping[nums[i]]++; if(maping[nums[i]]>mostCount) { mostCount=maping[nums[i]]; mostNum=nums[i]; } } return mostNum; } int main() { int A[]={1,1,1,1,2,4,4,4,4,4,4,4,4,5}; int len=(sizeof(A)/sizeof(A[0])); vector<int> nums(A,A+len); int mostNum=findMoreThanHalfNum(nums); cout<<mostNum<<endl; system("pause"); return 0; } /********************************************************************************************************************************************************************/ //方法二：先对数组排序，利用数组特性，数组中有一个数字出现的次数超过了数组长度的一半， //则数组中间的数（即中位数）为所求；最快的排序算法时间复杂度为O(nlogn)； /*******************************************************************************************************************************************************************/ //方法三：利用数组特性：数组中有一个数字出现的次数超过了数组长度的一半，即该数出现的次数比其他所有数出现的次数的和还要大； // 遍历数组，保存两个值，一个存储数组中的一个数字，一个存储次数；当我们遍历下一个数字时，若下一个数字与之前保存的 // 的数字相同，则次数加1；如果数字和之前保存的数字不同，则次数减-1,；如果次数为0，需要保存下一个数字，并把次数设为1； // 因为要找的数出现的次数比其他所有数出现的次数的和还要多，则要找的数字肯定是最后一次把次数设为1时对应的数字； int findMoreThanHalfNum(int *nums,int len) { if(nums==nullptr||len<=0) return -1; int findNum=nums[0]; int count=1; for(int i=1;i<len;i++) { if(count==0) { findNum=nums[i]; count=1; } else if(nums[i]==findNum) count++; else count--; } return findNum; }