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

9个回答

添加回答
推荐
思路:
1,对集合S进行
   查看全部
编辑于 2015-01-30 14:59:59 回复(12)
/*********************************
*   日期: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)
这个应该是3sum的变形吧
发表于 2017-08-16 16:41:13 回复(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 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋