1.给出一个有序数组啊,长度为len,另外给出第三个数X,问是否能在数组中找到两个数,这两个数之和等于第三个数X。
我们首先看到第一句话,这个数组是有序的,所以,我们可以定义两个指针,一个指向数组的第一个元素,另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值),首先计算两个位置的和是否等于给定的第三个数,如果等于则算法结束,如果大于,则尾指针向头指针方向移动,如果小于,则头指针向尾指针方向移动,当头指针大于等于尾指针时算法结束,没有找到这样的两个数。
解法一:
#include <stdio.h>
int judge(int *a, int len, int k, int *num1, int *num2);
int main(int argc, char **argv)
{
int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int result = -1;
int num1, num2;
result = judge(test_array, sizeof(test_array) / sizeof(int), 12, &num1, &num2);
if(result == 0)
{
printf("%d\t%d\n", num1, num2);
}
else if(result == -1)
{
printf("can't find");
}
else
{
printf("error");
}
}
int judge(int *a, int len, int k, int *num1, int *num2)
{
int *low = NULL;
int *high = NULL;
int i = 0;
int result = -1;
if(a == NULL || len < 2)
{
return result;
}
if(a[0] >= k)
{
return result;
}
while(a[i] <= k && i < len)
{
i++;
}
low = a;
high = a + i - 1;
while(low < high)
{
*num1 = *low;
*num2 = *high;
if((*low + *high) == k)
{
result = 0;
break;
}
else if((*low + *high) > k)
{
high--;
}
else if((*low + *high) < k)
{
low++;
}
}
return result;
}
解法二:
#include <iostream>
using namespace std;
int hash_table[100];
bool judge(int *a, int len, int x)
{
memset(hash_table, 0, sizeof(hash_table));
for (int i=0; i<len; ++i)
{
hash_table[x - a[i]] = 1;
}
for (int i=0; i<len; ++i)
{
if (hash_table[i] == 1)
{
return true;
}
}
return false;
}
int main()
{
int len = 10;
int a[10] = {1, 3, 5, 7, 9, 4, 2, 8, 10, 6};
int x = 19;
if (judge(a, len, x))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
system("pause");
return 0;
}
本题解决方法:hash table。
时间复杂度:O(N)
空间复杂度:O(N)
2.给定有n个数的数组a,其中有超过一半的数为一个定值,在不进行排序,不开设额外数组的情况下,以最高效的算法找出这个数。
int find(int* a, int n);
#include <iostream>
using namespace std;
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--;
}
}
}
return t;
}
int main()
{
int n = 10;
int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};
cout<<find(a, n)<<endl;
system("pause");
return 0;
}
Time Complexity: O(n)
Space Complexity:O(1)
转载请注明原创链接:http://blog.csdn.net/wujunokay/article/details/12209217
分享到:
相关推荐
求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘...
去哪儿网2014笔试算法题汇总:1.写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/new/../,输出路径为:/home/temp。 参考代码: 1. //写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/...
2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法...
华为校园招聘笔试算法题汇总.doc
2014华为校园招聘笔试算法题汇总.doc
华为OD、大厂笔试算法题; 一共87题,每一题附答案(java语言),笔试时频繁出现的原题,想进大厂的小伙伴,欢迎下载; eg: 1、5键键盘的输出 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键...
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
vue双向绑定原理,面试时自己拿来看的代码
12-02-28网易笔试一道算法题,附件代码是我自己的解题
部分IT公司笔试算法题,比较有用,让大家学习,很多有名算法!
兔子繁殖 半段质数 水仙花数 最大公约数 最小公倍数 数字排序等经典的编程问题
算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题
去哪儿网校园招聘笔试试题算法题汇总.docx去哪儿网校园招聘笔试试题算法题汇总.docx去哪儿网校园招聘笔试试题算法题汇总.docx去哪儿网校园招聘笔试试题算法题汇总.docx去哪儿网校园招聘笔试试题算法题汇总.docx去...
超多IT公司笔试算法题及具体答案……
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法,本人在准备笔试的时候找的,算法尽量采用最优的。 所有的代码均经过测试,个人觉得没有问题,如果哪位大牛找到错误,欢迎批评指正
IT公司笔试算法题 面试 笔试 经典体型。可以改。 非常使用。算法。数据结构
java笔试算法题及答案.doc java笔试算法题及答案.doc
多种笔试面试的算法设计题,和经典笔试题目。