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

8个回答

添加回答
  • 推荐
    思路:
    1,对集合S进行
       查看全部
    编辑于 2015-01-30 14:59:59 回复(10)
  • /*********************************
    *   日期: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;
    }
    
    时间复杂度O(n*n) 
    发表于 2015-01-29 22:47:25 回复(0)
  • ,,,,
    发表于 2017-02-23 21:26:13 回复(0)
  • leecode典型的2sum问题,先排序再从两头一个一个验证。
    发表于 2016-07-20 16:11:06 回复(0)
  • 可以首先使用归并排序,时间复杂度为nlogn,排序好后,利用两个指针,分别指向排序组的首尾,这样时间复杂度为n。
    发表于 2016-07-13 11:30:31 回复(0)
  • 时间复杂度可以降到O(n)
    发表于 2016-05-01 11:28:46 回复(0)

  • public class Findsunc {


    public static void main(String[] args) {

    // TODO Auto-generated method stub

    int s[] = {1,2,3,4,5,7,6,98};

    int ans = FindC(s);

    System. out .println(ans);

    }


    //查找满足C=A+B的最大值

    public static int FindC( int arr []){

    quick_sort(arr,0,arr.length-1);

    for ( int max = arr.length-1;max>1;max--){

    int C= arr[max];

    int i=0,j=max-1;

    while (j>i){

    if (arr[i]+arr[j]==C)

    return C;

    if (arr[i]+arr[j]<C){

    i++;

    }

    else {

    j--;

    System. out .println(arr[j]);

    }

    }

    }

    return -1;

    }

    static void quick_sort( int arr[], int left, int right) {

            int dp;

            if (left < right) {

                dp = partition(arr, left, right);

                quick_sort(arr, left, dp - 1);

                quick_sort(arr, dp + 1, right);

            }

        }

     

        static int partition( int arr[], int left, int right) {

            int pivot = arr[left];

            while (left < right) {

                while (left < right && arr[right] >= pivot)

                    right--;

                if (left < right)

                    arr[left++] = arr[right];

                while (left < right && arr[left] <= pivot)

                    left++;

                if (left < right)

                arr[right--] = arr[left];

            }

            arr[left] = pivot;

            return left;

    	    }

    发表于 2016-03-30 19:10:04 回复(0)
  • #include<cstdlib>
    #include<iostream>

    using namespace std;

    void quickSort(int my_array[], int left, int right);
    int devide(int my_array[], int left, int right);
    int getMax(int my_array[], int n);

    //快排
    int devide(int my_array[], int left, int right)
    {
        int key_number = my_array[left];
        do
        {
            while ((left < right) && my_array[right] >= key_number)
            {
                right--;
            }
            if (left < right)
            {
                my_array[left] = my_array[right];
                left++;
            }
            while ((left < right) && my_array[left] <= key_number)
            {
                left++;
            }
            if (left < right)
            {
                my_array[right] = my_array[left];
                right--;
            }
        } while (left != right);
        my_array[left] = key_number;
        return left;
    }
    void quickSort(int my_array[], int left, int right)
    {
        int mid;

        if (left >= right)
        {
            return;
        }
        mid = devide(my_array, left, right);
        quickSort(my_array, left, mid - 1);
        quickSort(my_array, mid + 1, right);
    }

    //筛选
    int getMax(int my_array[], int n)
    {
        int max = 0;
        int *my_array2;

        my_array2 = new int[n];
        for (int i1 = 0; i1 < n; i1++)
        {
            for (int i2 = n - 1; i2 >= i1 + 2; i2--)
            {
                my_array2[i2] = my_array[i2] - my_array[i1];
                for (int i3 = 0; i3 < i2; i3++)
                {
                    if (my_array2[i2] == my_array[i3])
                    {
                        if (my_array[i2] > max)
                        {
                            max = my_array[i2];
                            break;
                        }
                    }
                }
            }
        }
    }

    int main()
    {
    int number_of_integer;
    int *my_array1;
    int max;

    cin >> number_of_integer;
    my_array1 = new int[number_of_integer];
    for (int i1 = 0; i1 < number_of_integer; i1++)
    {
        cin >> my_array1[i1];
    }
    quickSort(my_array1, 0, number_of_integer - 1);

    max = getMax(my_array1, number_of_integer);

    if (max != 0)
    {
        cout << max << endl;
    }
    else
    {
        cout << "this kind of integer do not exist!" << endl;
    }

    system("pause");
    return 0;
    }
    发表于 2015-03-22 09:41:53 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋