`
SunnyYoona
  • 浏览: 361519 次
社区版块
存档分类
最新评论

[经典面试题][百度]在由N个正整数的集合S中,找出最大元素C,满足C=A + B

 
阅读更多

【题目】

在由N个正整数的集合S中,找出最大元素C,满足C=A + B其中A,B都是集合S中元素,请给出算法描述,代码与时间复杂度分析。

【分析】

1,对集合S进行排序(快排),从小到大排序
2,让C指向集合最后一个元素(最大元素)
3,让i指向S中第一个元素,让j指向C的前一个元素
4,如果,A[i]+A[j]==C则return C;
5,如果if(A[i]+A[j]<C)则i++;
6,如果if(A[i]+A[j]>C)则j--;
7,直道i>=j依然没有找到符合条件的元素,则C在S中向前移动一位,跳至步骤3

【代码】

/*********************************
*   日期:2015-01-29
*   作者:SJF0115
*   题目: 在由N个正整数的集合S中,找出最大元素C,满足C=A+B,其中A,B都是集合S中的元素
*   来源:百度
*   博客:
**********************************/
#include <iostream>
#include <algorithm>
using namespace std;

int FindSum(int A[],int n){
    // 排序
    sort(A,A+n);
    int left,right,sum;
    // i = C
    for(int i = n - 1;i >= 2;--i){
        left = 0,right = i - 1;
        // 判断是否有A + B = i
        while(left < right){
            sum = A[left] + A[right];
            if(sum == A[i]){
                return A[i];
            }//if
            else if(sum > A[i]){
                --right;
            }
            else{
                ++left;
            }
        }//while
    }//for
    return -1;
}

int main(){
    int A[] = {5,7,3,0,9,11,8,13,100};
    int n = 9;
    cout<<FindSum(A,n)<<endl;;
    return 0;
}


讨论:[百度]在由N个正整数的集合S中,找出最大元素C,满足C=A + B



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics