/*****************************************************************
题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现
了5次,超过数组长度的一半,因此输出2。
*****************************************************************/\
#include<stdio.h>
#include<iostream>
void swap(int* a, int* b)
{
int nTemp = *a;
*a = *b;
*b = nTemp;
}
int partition(int* numbers, int start, int end)
{
int standard = numbers[end];
int small = start - 1;
for(int i = start; i<end; ++i)
{
if(numbers[i]<standard)
{
++small;
if(i != small)
swap(&numbers[i],&numbers[small]);
}
}
++small;
swap(&numbers[small],&numbers[end]);
return small;
}
//方法一
//找排序后的中卫数,可以借鉴快速排序思想寻找中位数,复杂度为O(N)
int moreThanHalfNumber(int* numbers, int length)
{
//无效输入
if(numbers == NULL || length <= 0)
throw new std::exception("Invalid input!\n");
int middle = length >> 1;
int start = 0;
int end = length-1;
int index = partition(numbers,start,end);
while(index != middle)
{
if(index<middle)
{
start = index+1;
index = partition(numbers,start,end);
}
else
{
end = index-1;
index = partition(numbers,start,end);
}
}
int result = numbers[middle];
int times = 0;
for(int i=0; i<length; ++i)
{
if(numbers[i] == result)
++times;
}
if(times * 2 <= length)
throw new std::exception("Invalid input!\n");
else
return result;
}
//方法2
//遍历数组的时候保存两个值:一个是数组中的数字,一个是次数。当我们
//遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则、
//次数加1;如果下一个数字和我们之前保存的数字不同,则次数减1.如果次数
//为0,我们需要保存下一个数字,并把次数设为1.由于我们要找的数字出现的
//次数比其他所有数字出现的次数之和还多,那么要找的数字肯定是最后一次把
//次数设为1时对应的数字。
//复杂度为O(N)
int moreThanHalfNumber2(int* numbers, int length)
{
//无效输入
if(numbers == NULL || length <= 0)
throw new std::exception("Invalid input!\n");
int result = numbers[0];
int times = 1;
for(int i=1; i<length; ++i)
{
if(times == 0)
{
result = numbers[i];
times = 1;
}
else if(numbers[i] == result)
{
++times;
}
else
--times;
}
times = 0;
for(int i=0; i<length; ++i)
{
if(numbers[i] == result)
++times;
}
if(times * 2 <= length)
throw new std::exception("Invalid input!\n");
else
return result;
}
void test()
{
const int length = 9;
int numbers[length] = {1,2,3,2,2,2,5,4,2};
printf("%d\n",moreThanHalfNumber2(numbers,length));
}
int main()
{
test();
return 0;
}
分享到:
相关推荐
数组中出现次数超过一半的数字.md
数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2
java基础面试题数组中出现次数超过一半的数字本资源系百度网盘分享地址
在本篇文章中我们给大家分享了php如何实现数组中出现次数超过一半的数字的统计方法,有需要的朋友们参考下。
题目位置题解* 思路一:* 1、使用 map 存储每一个数字出现的次数,然后找到最大的* 思路二:* 1、数组中有一个数字出现的次数超过数组长度的一半 说明在这
【出现次数超过一半的数,它的出现次数比其他所有数字出现次数的总和还要多】这个操作的思想:(自己猜的)相当于将所有数分成两半 用最多的和其余每个抵消完 还有的话
# 返回most_common(k)的是最常出现的k个元素的(元素,次数)tuple组成的数组# 先从数组中取出最长出现(元素,次数)tuple,再分别从tup
如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 majority,或者有 majority,但是出现的次数少于 i / 2 ,因为如果
1. 题目描述 2. 思路分析 3. 代码
题目:数组中出现次数超过一半的数字 题:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
比较容易想到的思路是直接对数组排序,那中间那个值就是我们想要的值,但这样的想法明显排序后会对输入的数组顺序有影响,所以我们可能需要换一种思路。数组中有一个数字出
主要介绍了PHP实现找出数组中出现次数超过数组长度一半的数字算法,涉及php数组的遍历、统计、判断等相关操作技巧,需要的朋友可以参考下
主要介绍了基于Java代码实现数字在数组中出现次数超过一半的相关资料,需要的朋友可以参考下
主要介绍了Python 找出出现次数超过数组长度一半的元素实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
数组中出现次数超过一半的数字.py 最小的k个数.py 连续子数组的最大和.py n整数中1出现的次数.py 数字序列中的某一位数字.py 把数组拍成最小的数字.py 把数字翻译成字符串.py 礼物的最大价值.py 最长不含重复字符的...
39.数组中出现次数超过一半的数字 Array 常考 40.最小的k个数 Heap 41.数据流中的中位数 常考 42.连续子数组最大和 Dynamic Programming 43.整数中1出现的次数 Bit Manipulation 关注 44.数字序列中某一位的数字 ...
数组中出现次数超过一半的数字30.连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37.数字在排序数组中出现的次数40.数组中自出现过一次的数字50.数组中的重复数字51.构建乘积数组 数组篇 1.二维数组中的...
Java面试 Java超级经典100问题 Java高级开发工程师必备 Java面试宝典 ...数组中出现次数超过一半的数字.30.找出最小的K个数31.连续子数组的最大和.32.从1到整数n中1出现的次数.33.把数组中的数排成一个最小的数.3