剑指offer之数组出现次数超过一半的数字
1 问题
数组中有一个数字出现了次数超过数组长度的一半，请找出这个数字。
比如{1,2,3,2,2,2,5,4,2},我们知道这个数是2
2 分析
我们数组元素个数分为单数和双数
1）数组长度是单数的情况下
我们有5个元素，里面至少3个2，还有2个元素我们可能重复也可能不重复
我们可以定义一个计数为1，先用变量保存数组第一个数据，然后遍历数组，如果发现后面的数据和前面的数据不一样，我们计数自动减1，如果一样计量数自动加1，当计数为0的时候，我们变量保存数组后面的一个数，比如{2,1,1,2,2}，第二个1和第一个2抵消了，我们变量保存了第三个元素，但是第四元素值2和第3元素值也抵消了，最后的值也就是我么需要的值，如果是有2个不重复的数据比如，{1,3,2,2,2}，我们第一个元素和第二个元素的值抵消了，当计量等于0就保存数组下一个元素，然后计量数归1，也就是我们保存第三个元素，然后计量加1，到最后，计量大于1，保存的元素就是我们想要的结果。
2）数组长度是双数的情况下
比如6个元素，至少有4个元素一样，2个元素和这4个元素不一样，这2个元素可能重复也可能不重复，和上面的分析也一样，用一个计量和一个变量保存第一个数据，然后后面的元素和前一个元素不一样，我们计量数就自动加1，当计量等于0就保存数组下一个元素，然后计量数归1，最后计量数肯定大于1，然后我们最后保存变量也是我们想要的结果。
3 代码实现
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
/*
-
*检测这个数有没有超过数组元素一半值。
-
*/
-
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;
-
-
}
-
-
-
-
/*
-
*获取超过数组元素一半值这个数
-
*/
-
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 运行结果
-
moreNumber is 2
-
-
5 另外思路
分析：我们知道剑指offer之partition算法 可以找出一个数据，进行把所有数据分为左边小于其中的一个值，右边的大于一个值，既然题目说了 有一个数字出现了次数超过数组长度的一半，如果数组是奇数个数的话，比如{1,2,3,2,2};我们知道如果排序后最中间的数字就是2，也就是我们的中位数，如果数组是偶数个数的话，比如{1,2,3,2,2,2};这里不能只有3个2，不然3个其他数和题目逻辑矛盾，所以至少是4个2，然后我么进行求这个数组的中位数还是2，所以现在题目演变成了，如果这个数据排序好了，我们求出中位数就行，也就是通过partition算法求出返回值为(数组长度 / 2)的值，然后我们再获取数组下表是值为 数组长度 / 2 的数组值就行。
6 代码实现
-
#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类型，我们记得要加引用，
-
*不然改变不了数据，这里和java传递ArrayList不一样，ArrayList作为参数可以改变集合里面的值，
-
*所以C++如果函数传递非基本数据类型，一半都是带引用的
-
*/
-
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;
-
}
-
//这里用的数组赋值，而不是直接用swap交换函数，那么下面的2步也是用数组赋值，而不是用swap交换函数
-
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 运行结果
-
2 1 2 3 2 -1 2
-
-1 1 2 2 2 3 2
-
value is 2
-
-
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/102597430
- 点赞
- 收藏
- 关注作者
评论（0）