大都组k大数

给定两个有序数组arr1和arr2，在给定一个整数k，返回两个数组的全部数中第K小的数。
譬喻：
arr1 = {1,2,3,4,5};
arr2 = {3,5};
K = 1;
由于1为全部数中最小的，以是返回1；

arr1 = {1,3};
arr2 = {3,5,6};
K = 4;
由于3为全部数中第4小的数，以是返回3；

要求：假如arr1的长度为N，arr2的长度为M，时刻伟大度请到达O(log(min{M,N}))。

http://www.nowcoder.com/practice/952b97f197494378a437c1f11596dc63?tpId=49&tqId=29339&rp=4&ru=/ta/2016test&qru=/ta/2016test/question-ranking

大都组中位数

给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中全部数的上中位数。
譬喻：
arr1 = {1,4};
arr2 = {3,6};
一共8个数则上中位数是第4个数，以是返回3。

arr1 = {0,1,2};
arr2 = {3,5};
一共6个数则上中位数是第3个数，以是返回2。

要求：时刻伟大度O(logN)

http://www.nowcoder.com/practice/c001f4e9820447189110da5e882aa158?tpId=49&tqId=29340&rp=4&ru=/ta/2016test&qru=/ta/2016test/question-ranking

探求最小的k个数(进一步要求次序与原数组中元素次序同等)

http://www.voidcn.com/article/p-nabqeevw-wk.html

大都组k大数 AC代码

class Solution {
public:

    int findKthNum(vector<int> arr1,vector<int> arr2,int kth) {
        int len1 = arr1.size();
        int len2 = arr2.size();
        vector<int> shortArr = len1 < len2 ? arr1 : arr2;
        vector<int> longArr = len1 >= len2 ? arr1 : arr2;
        int lenS = shortArr.size();
        int lenL = longArr.size();

        if (kth < 1 || kth > len1 + len2) // kth不切合 直接返回
            return -1;

        if (kth <= lenS){
            return getUpMedian(shortArr,0,kth - 1,longArr,kth - 1);
        }
        if (kth > lenL){
            if (shortArr[kth - lenL - 1] >= longArr[lenL - 1]){
                return shortArr[kth - lenL - 1];
            }
            if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){
                return longArr[kth - lenS - 1];
            }
            return getUpMedian(shortArr,kth - lenL,lenS - 1,kth - lenS,lenL - 1);
        }

        if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){
            return longArr[kth - lenS - 1];
        }
        return getUpMedian(shortArr,kth - 1);
    }

    int getUpMedian(vector<int> arr1,int l1,int r1,int l2,int r2) {
    /* int N1 = arr1.size(); int N2 = arr2.size(); int l1 = 0,r1 = N1 - 1; int l2 = 0,r2 = N2 - 1;*/

        while (l1 != r1 || l2 != r2)
        {
            int mid1 = (l1 + r1) / 2;
            int mid2 = (l2 + r2) / 2;

            // 暗示 2分查找要不要包括中间谁人数 奇数是0，偶数是1
            int offset = (r1 - l1 + 1) & 1 ^ 1;

            if (arr1[mid1] > arr2[mid2])
            {
                l2 = mid2 + offset;
                r1 = mid1;
            }
            else if (arr2[mid2] > arr1[mid1]){
                l1 = mid1 + offset;
                r2 = mid2;
            }
            else{
                return arr1[mid1];
            }
        }// while

        return arr1[l1] < arr2[l2] ? arr1[l1] : arr2[l2];
    }
};

留意点：

• 求中位数 回收了二分思绪

• 求中卫数 用二分是 要留意长度为奇偶是纷歧样的（middle位置的数要不要取的题目），还要留意最后的处理赏罚

• 在求第k大数时，要分环境，裁减掉一些显然不满意的环境，转换为求中位数题目，这里必要对k的巨细分类接头，见代码.
  下面是个中一种环境的声名
  

  

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!