深圳英文网站建设去哪家,dede网站首页,wordpress tag_id,登记注册身份验证app下载1 问题
数组中有一个数字出现了次数超过数组长度的一半#xff0c;请找出这个数字。
比如{1,2,3,2,2,2,5,4,2},我们知道这个数是2 2 分析
我们数组元素个数分为单数和双数
1#xff09;数组长度是单数的情况下
我们有5个元素#xff0c;里面至少3个2#xff0c;还有2个…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;elsereturn -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;elsereturn -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 vectorusing namespace std;void swap(int* a, int* b)
{int temp *a;*a *b;*b temp;
}void printVector(vectorint 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(vectorint 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(vectorint 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()
{vectorint 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
