问题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+, last, pos);

    else if (left > pos)

        return searchmid(v,first,left-,pos);

    return left;

}

int main()

{

    int k,length;

    cin >> k;

    cin >> length;

    vector<int> v(length,);

    int pos = , 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, , length-, length/ -  + length%);

    //在数组前一部分寻找k个小于等于v[index]的数

    for (int j = ; j < k; ++j) {

        int max = INT_MIN;

        int max_pos;

        for (int i = ; i < index-j; ++i) {

            if (v[i] > max) {

                max = v[i];

                max_pos = i;

            }

        }

        swap(v[max_pos],v[index-j-]);

    }

    //在数组后一部分寻找k个大于等于v[index]的数

    for (int j = ; j < k; ++j) {

        int min = INT_MAX;

        int min_pos;

        for (int i = index + j + ; i < length; ++i) {

            if (v[i] < min) {

                min = v[i];

                min_pos = i;

            }

        }

        swap(v[min_pos],v[index+j+]);

    }

    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 ;

}

问题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, );

    for (int i = ; i < length; ++i)

        cin >> v[i];

    cin >> target;

    for (int i = ; i < length;++i) {

        for (int j = i + ; j < length; j++) {

            if (v[i] + v[j] == target) {

                cout << v[i];

                cout << " ";

                cout << v[j];

                cout << endl;

            }

        }

    }

    //system("pause");

    return ;

}

巴特西

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

问题1

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

输入

输出

思路

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

题目描述

输入

输出

思路

最新文章

热门文章