剑指offer之数组出现次数超过一半的数字

2024-05-29 12:38

本文主要是介绍剑指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;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 <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

 

这篇关于剑指offer之数组出现次数超过一半的数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1013675

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[