多数组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,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; } (编辑:湘西站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |