原链接是:
人人网2013笔试算法题汇总
2.给定有n个数的数组a,其中有超过一半的数为一个定值,在不进行排序,不开设额外数组的情况下,以最高效的算法找出这个数。
int find(int* a, int n);
这道题的算法还可以优化一下,那就是对于这种情况:3,3,3,3,3,3,4,4,4,4。因为个数是10个,当统计的个数大于一半,那就可以中止判断了。实现如下:
int find(int *a, int n)
{
int t = a[0];
int count = 0;
for (int i=0; i<n; ++i)
{
if (count == 0)
{
t = a[i];
count = 1;
continue;
}
else
{
if (a[i] == t)
{
count++;
}
else
{
count--;
}
//增加一个判断
if (count > n/2)
{
return t;
}
}
}
return t;
}
这样的话,
Time Complexity: O(n/2)
Space Complexity:O(1)
另外一个实现方法:
int find1(int *a, int n)
{
int nTotal=0;
int i;
int j;
int nMax=a[0];//最大值
int nAvg;//平均值
int nCount;
for (i=0; i< n; i++)
{
nTotal += a[i];
if (a[i]>nMax)
{
nMax = a[i];
}
}
nAvg = nTotal/n;
for (j=nAvg; j<=nMax; j++)
{
nCount = 0;
for (i=0; i< n; i++)
{
if (a[i] == j)
{
nCount++;
}
if (nCount > n/2)
{
return j;
}
}
}
return 0;
}
测试代码:
int main()
{
int n = 11;
//int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};
//int a[10] = {4, 3, 4, 3, 4, 3, 4, 3,3,3};
int a[11] = {3, 3, 3, 4, 4, 4, 4, 4,3,3,3};
//int a[10] = {3, 10, 10, 10, 10, 10, 10, 3, 3, 3};
cout<<find1(a, n)<<endl;
cout<<find(a, n)<<endl;
system("pause");
return 0;
}
测试结果就不贴了,有兴趣的朋友试试看。
转载请注明原创链接:http://blog.csdn.net/wujunokay/article/details/12227851
分享到:
相关推荐
分治算法求n个数的数组中找出第二个最大元素
有两个数组a,b,大小都为n,数组元素的值任意,无序 //要求:通过交换a,b中的元素,使数组a的元素之和与数组b的元素之和之间//的差最小?
给定一个数组,找出其中3个相加等于0的组合
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
求解找到数组A[1..n]中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)的算法,并分析其最坏情况的时间复杂度。
c# 中数组的算法,c# 中数组的算法 c# 中数组的算法,c# 中数组的算法
用递归算法编写求一个数组A中的最大元素;/****一个递归算法,求数组A中最大的元素***/ #include int Max(int A[], int i, int j) //求顺序表A中的最大元素 ……
生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合 php 笛卡尔积二维数组矩阵算法 生成多个组合
PHP实现一维数组的组合算法,欢迎下载和评论。
数据结构教程(JAVA语言描述) 设计一个算法,将含有n个整数元素的数组a[0..n-1]循环右移m位,要求算法的空间复杂度为O(1)
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
题目: 编程实现找出一组数的最大值和次大值 要求: 用二分法的策略实现; (2)写出实验报告。 一、 需求分析: 1、输入要输入数组元素的个数,为数组分配存储空间(动态数组); 2、输入数组元素; 3、利用二分法...
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] ...
数组和常用算法
最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...
这篇文章主要介绍了JS合并两个数组的3种方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...这里有一个问题,concat方法连接a、b两个数组后,a、b两个数组的数据不变,同时会返
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...
填写下述del函数内容,功能是删除整型数组中指定的数。 如:数组中的数为: 4、8、9、7、0、1要删除的数为 9; 删除后数组中的值为:4、8、7、0、1 要求:写出算法思路分析的过程。 编写函数fun,函数的功能是:将...