多数组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的大小分类讨论，见代码.
  下面是其中一种情况的说明
  

  

（编辑：核心网）

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