算法导论练习题 2.3-7

偏执的太偏执、 2021-12-13 02:49 230阅读 0赞

\[淘宝笔试题，哪年出的题不记得了\]

请给出一个运行时间为O(nlgn)的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素？

1、先对数组排序，然后利用折半查找实现。

1 #include <iostream>
     2 using namespace std;
     3 
     4 void sort(int a[],int size)
     5 {
     6     // 直接插入排序
     7     int key =0;
     8     for(int i=1;i<size;++i)
     9     {
    10         key = a[i];
    11         int j;
    12         for(j=i-1;j>=0;--j)
    13         {
    14             if(a[j] > a[key]) 
    15                 a[j+1] = a[j];
    16             else
    17                 break;
    18         }
    19         a[j+1] = key;
    20     }
    21 }
    22 bool b_query(int a[],int size,int _x)
    23 {
    24     int low = 0;
    25     int high = size-1;
    26     int key = _x;
    27     while(low <= high)
    28     {
    29         int mid = (low+high)/2;
    30         if(a[mid] == key) return true;
    31         if(a[mid] < key) 
    32             low = mid + 1; 
    33         else if(a[mid] > key)
    34             high = mid - 1;
    35     }
    36     return false;
    37 }
    38 bool query_x(int a[],int size,int x)
    39 {
    40     sort(a,size);
    41     for(int i=0;i<size;++i)
    42     {
    43         if(true == b_query(a,size,x-a[i]))
    44             return true;
    45     }
    46     return false;
    47 }
    48 void main()
    49 {
    50     int a[] = {-10,10,5,9,-90,30,8,7,4,3};
    51     int x;
    52     cin >> x;
    53     if(true == query_x(a,10,x))
    54         cout << " 找到" <<endl;
    55     else
    56         cout << "未找到" << endl;
    57 
    58 }

2、利用hash\_set实现

1 #include <iostream>
     2 #include <hash_set>   // 注意要使用hash_set时，需要关联的头文件的格式
     3 #include <algorithm>    
     4 using namespace std;
     5 using namespace stdext;  // 注意要使用hash_set时，需要关联的命名空间格式  
     6 
     7 bool query_x(int a[],int size,int x)
     8 {
     9     hash_set<int> haset;
    10     for(int i=0;i<size;++i)
    11         haset.insert(haset.end(),a[i]);
    12     for(int i=0;i<size;++i)
    13     {
    14         hash_set<int>::iterator ip;
    15         ip = find(haset.begin(),haset.end(),x-a[i]); // 时间复杂度是O(1)
    16         if(ip != haset.end())
    17             return true;
    18     }
    19     return false;
    20 }
    21 void main()
    22 {
    23     int a[] = {-10,10,5,9,-90,30,8,7,4,3};
    24     int x;
    25     cin >> x;
    26     if(true == query_x(a,10,x))
    27         cout << " 找到" <<endl;
    28     else
    29         cout << "未找到" << endl;
    30 
    31 }

转载于:https://www.cnblogs.com/xuxu8511/archive/2012/04/12/2443594.html