個人中心
退出
劍指offer之數(shù)組出現(xiàn)次數(shù)超過一半的數(shù)字
1 問題
數(shù)組中有一個數(shù)字出現(xiàn)了次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。
比如{1,2,3,2,2,2,5,4,2},我們知道這個數(shù)是2
2 分析
我們數(shù)組元素個數(shù)分為單數(shù)和雙數(shù)
1）數(shù)組長度是單數(shù)的情況下
我們有5個元素，里面至少3個2，還有2個元素我們可能重復(fù)也可能不重復(fù)
我們可以定義一個計數(shù)為1，先用變量保存數(shù)組第一個數(shù)據(jù)，然后遍歷數(shù)組，如果發(fā)現(xiàn)后面的數(shù)據(jù)和前面的數(shù)據(jù)不一樣，我們計數(shù)自動減1，如果一樣計量數(shù)自動加1，當計數(shù)為0的時候，我們變量保存數(shù)組后面的一個數(shù)，比如{2,1,1,2,2}，第二個1和第一個2抵消了，我們變量保存了第三個元素，但是第四元素值2和第3元素值也抵消了，最后的值也就是我么需要的值，如果是有2個不重復(fù)的數(shù)據(jù)比如，{1,3,2,2,2}，我們第一個元素和第二個元素的值抵消了，當計量等于0就保存數(shù)組下一個元素，然后計量數(shù)歸1，也就是我們保存第三個元素，然后計量加1，到最后，計量大于1，保存的元素就是我們想要的結(jié)果。
2）數(shù)組長度是雙數(shù)的情況下
比如6個元素，至少有4個元素一樣，2個元素和這4個元素不一樣，這2個元素可能重復(fù)也可能不重復(fù)，和上面的分析也一樣，用一個計量和一個變量保存第一個數(shù)據(jù)，然后后面的元素和前一個元素不一樣，我們計量數(shù)就自動加1，當計量等于0就保存數(shù)組下一個元素，然后計量數(shù)歸1，最后計量數(shù)肯定大于1，然后我們最后保存變量也是我們想要的結(jié)果。
3 代碼實現(xiàn)
#include <stdio.h>
#include <stdlib.h>
/*
*檢測這個數(shù)有沒有超過數(shù)組元素一半值。
*/
int checkMoreThanHalf(int *datas, int length, int number)
{
if (datas == NULL || length <= 0)
{
return -1;
}
int count = 0;
for (int i = 0; i < length; ++i)
{
if (number == datas[i])
++count;
}
if (count * 2 > length)
return 1;
else
return -1;
}
/*
*獲取超過數(shù)組元素一半值這個數(shù)
*/
int getMoreThanHalf(int* datas, int length)
{
if (NULL == datas || length <= 0)
return 0;
int result = datas[0];
int times = 1;
for (int i = 1; i < length; ++i)
{
if (times == 0)
{
result = datas[i];
times = 1;
continue;
}
if (datas[i] == result)
{
++times;
}
else
{
--times;
}
}
int check = checkMoreThanHalf(datas, length, result);
if (check)
return result;
else
return -1;
}
int main(void)
{
int a[] = {2, 1, 2, 3, 2};
int moreNumber = getMoreThanHalf(a, sizeof(a) / sizeof(int));
printf("moreNumber is %d\n", moreNumber);
return 0;
}
4 運行結(jié)果
moreNumber is 2
5 另外思路
分析：我們知道劍指offer之partition算法 可以找出一個數(shù)據(jù)，進行把所有數(shù)據(jù)分為左邊小于其中的一個值，右邊的大于一個值，既然題目說了 有一個數(shù)字出現(xiàn)了次數(shù)超過數(shù)組長度的一半，如果數(shù)組是奇數(shù)個數(shù)的話，比如{1,2,3,2,2};我們知道如果排序后最中間的數(shù)字就是2，也就是我們的中位數(shù)，如果數(shù)組是偶數(shù)個數(shù)的話，比如{1,2,3,2,2,2};這里不能只有3個2，不然3個其他數(shù)和題目邏輯矛盾，所以至少是4個2，然后我么進行求這個數(shù)組的中位數(shù)還是2，所以現(xiàn)在題目演變成了，如果這個數(shù)據(jù)排序好了，我們求出中位數(shù)就行，也就是通過partition算法求出返回值為(數(shù)組長度 / 2)的值，然后我們再獲取數(shù)組下表是值為 數(shù)組長度 / 2 的數(shù)組值就行。
6 代碼實現(xiàn)
#include <iostream>
#include <vector>
using namespace std;
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void printVector(vector<int> v)
{
for (int i = 0; i < v.size(); ++i)
{
std::cout << v[i] << "\t";
}
std::cout << std::endl;
}
/*
*partition算法 記得如果這里是C++我們傳遞的是vector類型，我們記得要加引用，
*不然改變不了數(shù)據(jù)，這里和java傳遞ArrayList不一樣，ArrayList作為參數(shù)可以改變集合里面的值，
*所以C++如果函數(shù)傳遞非基本數(shù)據(jù)類型，一半都是帶引用的
*/
int partitionOne(vector<int>& vector, int start, int end)
{
if (start > end)
{
std::cout << "vector is empty or start > end" << std::endl;
return -1;
}
int pivot = vector[start];
while (start < end)
{
//我們先從尾巴開始
while (start < end && pivot <= vector[end])
{
--end;
}
//這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
vector[start] = vector[end];
while (start < end && pivot >= vector[start])
{
++start;
}
vector[end] = vector[start];
}
//std:cout << "start is " << start << "end is " << end << std::endl;
vector[start] = pivot;
//printVector(vector);
return start;
}
void getMoreThanHalf(vector<int>& vector)
{
if (vector.size() <= 0)
{
std::cout << "vector.size is <= 0" << std::endl;
return;
}
int start = 0;
int end = vector.size() - 1;
int middle = vector.size() / 2;
int index = partitionOne(vector, start, end);
printVector(vector);
while (index != middle)
{
if (index > middle)
{
end = index - 1;
index = partitionOne(vector, start, end);
}
else
{
start = index + 1;
index = partitionOne(vector, start, end);
}
}
}
int main()
{
vector<int> v2;
v2.push_back(2);
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(2);
v2.push_back(-1);
v2.push_back(2);
printVector(v2);
int a[] = {2, 1, 2, 3, 2};
getMoreThanHalf(v2);
std::cout << "value is " << v2[v2.size() / 2] << std::endl;
return 0;
}
7 運行結(jié)果
2 1 2 3 2 -1 2
-1 1 2 2 2 3 2
value is 2
作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)
分類導(dǎo)航