编写一个function,判断一个存有递增数列的数组中是否存在两个数的和等于给定的数字k(数列中的数字不重复),要求时间小于O(N^2), 使用【递归】算法。
(JAVA和C都可以,最好使用JAVA,谢谢帮助)
时间复杂度O(nlogn) 优于O(N^2)
#include <stdio.h>
#include <stdlib.h>
#define SUM_OK1
#define SUM_FAIL0
typedef struct _Pair{
int a;
int b;
}Pair;
static Pair ret;
int sum_binary_search( int * datas, int start, int len, int match )
{
int low =-1;
int pos = -1;
//为了便于测试 固定len是10 然后以下数据也都可以先写死进去
if (datas[7]<match) low = 10-8;
//assert(datas[low]<match && datas[low+8]>=match)
if (datas[low+4]<match) low += 4;
//assert(datas[low]<match && datas[low+4]>=match)
if (datas[low+2]<match) low += 2;
//assert(datas[low]<match && datas[low+2]>=match)
if (datas[low+1]<match) low += 1;
//assert(datas[low]<match && datas[low+1]>=match)
pos = low+1;
if (pos>10 || datas[pos]!=match)
{
pos = -1;
}
else{
ret.b = datas[pos];
}
return pos;
}
int search_pair( int * datas, int sum, int len )
{
int i;
int retVal = SUM_FAIL;
int *pair_datas = (int*)calloc(len,sizeof(int));
for (i = 0;i<len;i++)
pair_datas[i] = sum -datas[i];
for (i = 0;i<len;i++) //O(n)
{
ret.a = sum - pair_datas[i];
if (-1 != sum_binary_search(datas,0,len,pair_datas[i])) //O(lgn)
{
retVal = SUM_OK;
printf("(%d,%d)\n",ret.a,ret.b);
break;//----------要想打印出所有合适的结果去掉这个break即可 你自己使用入参来控制即可
}
} //-----> O(nlgn)
free(pair_datas);
pair_datas = NULL;
return retVal;
}
int compare(const void* a,const void* b){
int* t = (int*)a;int* s = (int*)b;
return (*t-*s);
}
int main(){
int (*cmp)(const void*,const void*) = compare;
int datas[10] = {2,10,5,3,4,6,13,7,11,9};
int sum = 13;
int len = 10;
qsort(datas,len,sizeof(int),cmp);
search_pair(datas,sum,len);
return EXIT_SUCCESS;
}追问
#include <stdio.h>
#include <stdlib.h>
#define SUM_OK1
#define SUM_FAIL0
typedef struct _Pair{
int a;
int b;
}Pair;
static Pair ret;
int sum_binary_search( int * datas, int start, int len, int match )
{
int low =-1;
int pos = -1;
//为了便于测试 固定len是10 然后以下数据也都可以先写死进去
if (datas[7]<match) low = 10-8;
//assert(datas[low]<match && datas[low+8]>=match)
if (datas[low+4]<match) low += 4;
//assert(datas[low]<match && datas[low+4]>=match)
if (datas[low+2]<match) low += 2;
//assert(datas[low]<match && datas[low+2]>=match)
if (datas[low+1]<match) low += 1;
//assert(datas[low]<match && datas[low+1]>=match)
pos = low+1;
if (pos>10 || datas[pos]!=match)
{
pos = -1;
}
else{
ret.b = datas[pos];
}
return pos;
}
int search_pair( int * datas, int sum, int len )
{
int i;
int retVal = SUM_FAIL;
int *pair_datas = (int*)calloc(len,sizeof(int));
for (i = 0;i<len;i++)
pair_datas[i] = sum -datas[i];
for (i = 0;i<len;i++) //O(n)
{
ret.a = sum - pair_datas[i];
if (-1 != sum_binary_search(datas,0,len,pair_datas[i])) //O(lgn)
{
retVal = SUM_OK;
printf("(%d,%d)\n",ret.a,ret.b);
break;//----------要想打印出所有合适的结果去掉这个break即可 你自己使用入参来控制即可
}
} //-----> O(nlgn)
free(pair_datas);
pair_datas = NULL;
return retVal;
}
int compare(const void* a,const void* b){
int* t = (int*)a;int* s = (int*)b;
return (*t-*s);
}
int main(){
int (*cmp)(const void*,const void*) = compare;
int datas[10] = {2,10,5,3,4,6,13,7,11,9};
int sum = 13;
int len = 10;
qsort(datas,len,sizeof(int),cmp);
search_pair(datas,sum,len);
return EXIT_SUCCESS;
}追问
感谢帮忙,对C语言我不是非常了解,在search_pair中有一个calloc似乎没有定义就可以使用,是stdlib.h中的吗?做什么用的呢?还有好像search_pair并没有用到递归?
追答在stdlib.h中 用于分配一块区域,并且将该块区域初始化为0,没看到递归的说明,所以确实没用到
温馨提示:答案为网友推荐,仅供参考