2017年生態(tài)文明你我共建征文
1.給出一個(gè)有序數(shù)組啊，長(zhǎng)度為len，另外給出第三個(gè)數(shù)X，問(wèn)是否能在數(shù)組中找到兩個(gè)數(shù)，這兩個(gè)數(shù)之和等于第三個(gè)數(shù)X。
我們首先看到第一句話，這個(gè)數(shù)組是有序的，所以，我們可以定義兩個(gè)指針，一個(gè)指向數(shù)組的第一個(gè)元素，另一個(gè)指向應(yīng)該指向的位置(這個(gè)需要看具體的實(shí)現(xiàn)和數(shù)組給定的值)，首先計(jì)算兩個(gè)位置的和是否等于給定的第三個(gè)數(shù)，如果等于則算法結(jié)束，如果大于，則尾指針向頭指針?lè)较蛞苿?dòng)，如果小于，則頭指針向尾指針?lè)较蛞苿?dòng)，當(dāng)頭指針大于等于尾指針時(shí)算法結(jié)束，沒(méi)有找到這樣的兩個(gè)數(shù)。
解法一：
#include
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
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
{
hash_table[x - a[i]] = 1;
}
for (int i=0; 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"<
}
else
{
cout<<"No"<
}
system("pause");
return 0;
}
本題解決方法：hash table。
時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)
2.給定有n個(gè)數(shù)的數(shù)組a，其中有超過(guò)一半的數(shù)為一個(gè)定值，在不進(jìn)行排序，不開設(shè)額外數(shù)組的情況下，以最高效的算法找出這個(gè)數(shù)。
int find(int* a, int n);
#include
using namespace std;
int find(int *a, int n)
{
int t = a[0];
int count = 0;
for (int i=0; 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<
system("pause");
return 0;
}
Time Complexity: O(n)
Space Complexity:O(1)
【生態(tài)文明你我共建征文】相關(guān)文章：
最新生態(tài)文明你我共建征文23篇01-06
生態(tài)文明你我共建的作文通用07-29
守護(hù)你我的生態(tài)文明作文06-05
共建生態(tài)文明，共享綠色未來(lái)的作文03-09
（薦）共建生態(tài)文明，共享綠色未來(lái)的作文05-08
弘揚(yáng)生態(tài)文明共建綠色校園的800字作文07-22
共建生態(tài)文明,共享綠色未來(lái)作文1000字06-16
生態(tài)文明從我做起征文600字08-09
(熱)共建生態(tài)文明，共享綠色未來(lái)作文1000字23篇09-10
- 最新生態(tài)文明你我共建征文 推薦度：
- 相關(guān)推薦