人人公司 2018校招 开发方向在线考试

编程题|30.0分1/2

明明上数学课-第K大数字

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB

题目描述：

明明又上数学课啦。

今天老师上课教了大家数大小，为了看看大家对这个问题的掌握程度，于是给大家留了一些作业，可是明明并不太会只能求助你了。

每道作业题会给大家n个整数，让大家求出这些整数中第k大的数字，值得注意的是这些数字可以相同，例如三个数字2，2，3。那么第1，2，3大分别为3，2，2.

2 <= k <= n <= 1000 给定整数在int范围内



输入

第一行两个整数n和k。

第二行n个用空格隔开的整数。



输出

输出一个数表示答案



样例输入

5 2
1 2 3 4 5
样例输出

4

使用快排思想找第K大的数，算法复杂度O（n）。

1.以数组a的第0位a[0]为参考基准base，将数组划分为两个部分； 
如果找第K大的数，则将大于base的数往前挪，将小于base的数往后挪。如果找第K小的数，则与此相反。 
划分过程与快排相同，使用两个指针i和j分别指向数组的首尾，根据指针所指元素与基准base的大小交替移动两个指针，直到两个指针指向同一个位置i==j，此时i或j即为base的下标.

2.当K-1大于base的索引i（或j）时，所要找的第K大的数位于base的后半部分，需要对后半部分进行排序，而不用管前半部分的顺序； 
当K-1小于base的索引时，所要找的第K大的数位于base的前半部分，只需要对前半部分进行排序； 
当K-1等于base的索引时，说明当前的base就是所要找的第K大的数。

使用递归方法对所需要排序的部分进行排序。

#include <iostream>
#include <vector>
using namespace std;

// 找第K小的数
void findKthSmaller(vector<int> &a, int K, int m,int n) {
    int base=a[m];

    int i=m,j=n;
    while(i<j){
        while(i<j && a[j]>=base){
            --j;
        }
        if(a[j]<base){
            a[i++]=a[j];
        }
        while(i<j && a[i]<base){
            ++i;
        }
        if(a[i]>=base){
            a[j--]=a[i];
        }
    }
    a[i]=base;

    if(K-1<i){
        findKthSmaller(a,K,m,i-1);
    }
    else if(K-1>i){
        findKthSmaller(a,K,i+1,n);
    }
    else
        return;
}

// 找第K大的数
// m,n表示所需要排序部分的首尾索引
void findKthBigger(vector<int> &a, int K, int m,int n) {
    int i=m,j=n;
    int base = a[i];
    while(i<j){
        while(i<j && a[j]<base){
            --j;
        }
        if(i<j)
            a[i++] = a[j];
        while(i<j && a[i]>=base){
            ++i;
        }
        if(i<j){
            a[j--] = a[i];
        }
    }
    a[i] = base;
    if(K-1 > i){
        findKthBigger(a,K,i+1,n);
    }
    if(K-1 < i){
        findKthBigger(a,K,m,i-1);
    }
    else
        return;
}

int main()
{
    vector<int> a;int n=10; int K=7;
    // 8 4 6 9 2 3 7 9 11 10
    for(int i=0;i<n;++i){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    findKthBigger(a,K,0,n-1);
    for(int i=0;i<n;++i){
        cout<<a[i]<<" ";
    }
    cout << endl;
    cout<< a[K-1] << endl;
    return 0;
}

编程题 | 30.0分2/2
面试
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB
题目描述：
由于小C明年就要毕业了，所以他开始参加秋招，今天的面试官非常nice，给了他这样一道题目：给N个数字，这N个数字就是从1到N，从这N个数字中选出K个数字，使这K个数字的异或值最大。

输入
输入有一行。

N和K（1≤K≤N≤10^18）

输出
输出最大的异或值


样例输入
4 3
样例输出
7

题意：给出1~n这n个数，最多选k个数，要求，选出的数的异或和最大，求这个异或和。

贪心、构造、位运算、异或和

首先对于n的二进制有b位，n ^ ((1<<b) - 1)的值必定小于n。

所以如果k为1，则只能选ans = n；

否则选n和n ^ ((1<<b) - 1)这2个数，当n和 ((1<<b) - 1)相等时依然选n，即 ans = (1<<b) - 1。

#include <iostream>
#include <cstdio>
 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;
 
 
int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
 
    LL n, k, ans = 0;
    cin >> n >> k;
    if(k == 1) cout << n << endl;
    else{
        while(n){
            ans <<= 1ll;
            ans |= 1ll;
            n >>= 1ll;
        }
        cout << ans << endl;
 
    }
 
 
 
    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}