南大算法设计与分析课程OJ答案代码（1）中位数附近2k+1个数、任意两数之和是否等于给定数

问题1

用来测试的，就不说了

问题2：中位数附近2k+1个数

给出一串整型数 a₁,a₂,...,a_n以及一个较小的常数 k，找出这串数的中位数 m 和最接近 m 的小于等于 m 的 k 个数，以及最接近 m 的大于等于 m 的 k 个数。将这 2k+1 个数按升序排序后输出。

中位数定义：如果数串的大小是偶数 2j，中位数是从小到大排列的第 j 个数；如果数串的大小是奇数 2j+1，中位数是从小到大排列的第 j+1 个数。

输入

第一行是 k 的值和数串的长度 n。

第二行是以空格隔开的 n 个整型数，最后一个数后面有空格。

输出

按升序排列的 2k+1 个数，以空格分开，最后一个数后面没有空格。结果可能出现重复的数。

思路

　　这题如果直接排序再输出是会超时的，排序算法的复杂度为nlgn，后来按照快排的思想做通过了。

　　先以快排的思想找出中位数，复杂度为n（递归方程为T(n)=T(n/2)+n，用代入法就可以证明），（由于快排是随机选取一个数做标准，所以我们在排完一次后需要判断所选标准和中位数的差距，接着在子区间内继续寻找中位数，选取到中位数后返回，具体看searchmid函数，应该写得很简洁了）

　　按照快排的思想，我们已经将数组分为小于中位数的区间，中位数，大于中位数的区间。根据题目，所给的k很小，再根据选择排序的思想在左右两区间各选取k个数即可。

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

//使用快速排序的思路，找出中间数，first和last为区间，pos为要寻找有序状态下的第几个数
int searchmid(vector<int>& v,int first, int last, int pos) {
    int left = first;
    int key = last;
    for (int i = first; i <= last; ++i) {
        if (v[i] < v[key]) {
            swap(v[i], v[left]);
            left++;
        }
    }
    swap(v[left], v[key]);
    if (left < pos)
        return searchmid(v, left+1, last, pos);
    else if (left > pos)
        return searchmid(v,first,left-1,pos);
    return left;
}

int main()
{
    int k,length;
    cin >> k;
    cin >> length;
    vector<int> v(length,0);
    int pos = 0, num;
    while (cin >> num) {
        v[pos] = num;
        pos++;
    }

    /*int k = 0;
    vector<int> v = {34, 10,9,8,7,6,5,4,3,2,1,0};
    int length = v.size();*/

    vector<int> result;
    int index = searchmid(v, 0, length-1, length/2 - 1 + length%2);
    //在数组前一部分寻找k个小于等于v[index]的数
    for (int j = 0; j < k; ++j) {
        int max = INT_MIN;
        int max_pos;
        for (int i = 0; i < index-j; ++i) {
            if (v[i] > max) {
                max = v[i];
                max_pos = i;
            }
        }
        swap(v[max_pos],v[index-j-1]);
    }
    //在数组后一部分寻找k个大于等于v[index]的数
    for (int j = 0; j < k; ++j) {
        int min = INT_MAX;
        int min_pos;
        for (int i = index + j + 1; i < length; ++i) {
            if (v[i] < min) {
                min = v[i];
                min_pos = i;
            }
        }
        swap(v[min_pos],v[index+j+1]);
    }
    for (int i = index - k; i <= index + k; i++) {
        cout << v[i] ;
        if (i != index + k)
            cout << " ";
    }
    /*cout << endl;

    sort(v.begin(), v.end());
    for (auto h : v)
        cout << h << " ";
    cout << endl;

    system("pause");*/
    return 0;
}

View Code

问题3：任意两数之和是否等于给定数

题目描述

给定一个 int 数组 arr，元素按照升序排列且各不相同。另外有一个目标数 c，请你找出 arr 中所有的数对 a, b，使得 a + b = c。

输入

输入为三行，第一行为 arr 的元素个数，第二行为 arr，元素以空格分隔，第三行为目标数 c。

输出

所有符合条件的数对 a, b。a 和 b 以空格分开，每个数对占据一行。每行中 a < b，所有数对以它的第一个数（也就是 a 的值）升序排列。

思路

直接遍历判断，符合条件的直接输出就可以了。

int main()
{
    int length;
    int target;
    cin >> length;
    vector<int> v(length, 0);
    for (int i = 0; i < length; ++i)
        cin >> v[i];
    cin >> target;

    for (int i = 0; i < length;++i) {
        for (int j = i + 1; j < length; j++) {
            if (v[i] + v[j] == target) {
                cout << v[i];
                cout << " ";
                cout << v[j];
                cout << endl;
            }
        }
    }

    //system("pause");
    return 0;
}

View Code