溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
題：數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。
思路：首先看到這個題目，數組中一個數字出現的次數超過數組長度的一半，也就意味著這個數字出現的次數比數組中其它數字出現次數的總和還多。我們在遍歷的數組的時候可以用兩個值來記錄，一個是數組出現的次數count,一個用來保存它的結果result,我們把數組的第一個數arr[0]作為結果保存跟下一個數字比較，count記為1，如果下一個數字跟之前保存的數字相同count+1,如果跟之前保存的數字不同，則count-1。如果次數為0，我們需要保存它的下一個數字，并且將次數設為1。因為要找的數字出現的次數超過數組長度長度的一半，所以最后一次設為1的數字就是我們要找的數字。
代碼：
#include <iostream>
using namespace std;
int Serach(int arr[],int len)
{
int count=1;
int result=arr[0];
for(int i=1;i<len;i++)
{
if(count==0)
{
result=arr[i];
count=1;
}
else if(result == arr[i])
count++;
else
count--;
}
return result;
}
int main()
{
int arr[]={1,2,3,2,2,2,5,4,2};
int sz=sizeof(arr)/sizeof(arr[0]);
int ret=Serach(arr,sz);
cout<<ret<<endl;
return 0;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
