首页 > 试题广场 >

在由N个正整数的集合S中，找出最大元素C，满足C=A+B,其

[问答题]

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

推荐

牛客-007

思路：

1，对集合S进行排序（快排），从小到大排序

2，让C指向集合最后一个元素（最大元素）

3，让i指向S中第一个元素，让j指向C的前一个元素

4，如果，arr[i]+arr[j]==C则return C;

5，如果if(arr[i]+arr[j]<C)则i++;

6，如果if(arr[i]+arr[j]>C)则j--;

7，直道i>=j依然没有找到符合条件的元素，则C在S中向前移动一位，跳至步骤3

java代码如下：

public class FindSum {

 public static void main(String[] args) {
 // TODO Auto-generated method stub

 int [] array={5,7,3,0,9,11,8,13,100};//测试数据
 int res = findC(array);
 System.out.println(res);//输出13
 }
 
 //查找满足C=A+B的最大C值
 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--;
 }
 }
 return -1; 
 }

 //快速排序算法
 public static void quick_sort(int arr[], int L, int R) {

 if (L < R) {
 int tmp = arr[L];
 int index_lift = L, index_right = R;
 while (index_lift < index_right) {
 while (index_lift < index_right && arr[index_right] >= tmp)
 index_right--;
 if (index_lift < index_right)
 arr[index_lift++] = arr[index_right];

 while (index_lift < index_right && arr[index_lift] < tmp)
 index_lift++;
 if (index_lift < index_right)
 arr[index_right--] = arr[index_lift];
 }
 arr[index_lift] = tmp;
 quick_sort(arr, L, index_right - 1);
 quick_sort(arr, index_lift + 1, R);
 }
 }
 }

快排的时间复杂度为O(nlogn),查找的时间复杂度为O（n*n)

总的时间复杂度取较大者，为O（n*n）

编辑于 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)

朔东风

n^2

发表于 2017-12-21 12:52:58 回复(0)

Initial_q

这个应该是3sum的变形吧

发表于 2017-08-16 16:41:13 回复(0)

牛客9588691号

，，，，

发表于 2017-02-23 21:26:13 回复(0)

Toktok

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)

Alpha.Tan

#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)

提交观点

问题信息

百度查找

上传者：小牧魔法袋

难度：

10条回答 77收藏 13217浏览

在由N个正整数的集合S中，找出最大元素C，满足C=A+B,其

问题信息

热门推荐

相关试题