加入收藏 | 设为首页 | 会员中心 | 我要投稿 湘西站长网 (https://www.0743zz.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

多数组K大数

发布时间:2021-01-21 20:39:24 所属栏目:大数据 来源:网络整理
导读:题目描述 给定两个有序数组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小的数,所以

题目描述

给定两个有序数组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}))。

//多数组K大数
    public int findKthNum(int[] arr1,int[] arr2,int kth) {
        int len1 = arr1.length;
        int len2 = arr2.length;
        int k = 0;
        int i =0;
        int j =0;
        int result;
        while (i < len1 && j < len2) {
            if (arr1[i] < arr2[j]) {
                result = arr1[i];
                ++i;
            }else {
                result = arr2[j];
                ++j;
            }
            ++k;
            if (k == kth) {
                return result;
            }
        }
        while (i < len1) {
            ++k;
            if (k == kth) {
                return arr1[i];
            }
            ++i;
        }
        while (j < len2) {
            ++k;
            if (k == kth) {
                return arr2[j];
            }
            ++j;
        }
        return 0;
    }

(编辑:湘西站长网)

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

    热点阅读