如何在两个sorting数组的并集中find第k个最小的元素？

这是一个功课问题。 他们说这需要O(logN + logM) ，其中N和M是数组的长度。

我们来命名数组a和b 。 显然，我们可以忽略所有的a[i]和b[i] ，其中i> k。
首先我们来比较a[k/2]和b[k/2] 。 令b[k/2] > a[k/2] 。 所以我们也可以丢弃所有的b[i] ，其中i> k / 2。

现在我们有a[i] ，其中我<k和所有b[i] ，其中我<k / 2find答案。

你下一步怎么做？

Answer 1

你知道了，继续下去！ 并小心索引…

为了简化一下，我假设N和M> k，所以这里的复杂度是O（log k），它是O（log N + log M）。

伪代码：

 i = k/2 j = k - i step = k/4 while step > 0 if a[i-1] > b[j-1] i -= step j += step else i += step j -= step step /= 2 if a[i-1] > b[j-1] return a[i-1] else return b[j-1] 

对于演示，你可以使用循环不变i + j = k，但我不会做所有的功课:)

Answer 2

自从问这个问题以来，我希望我不回答你的功课。 这是一个尾recursion的解决scheme，将采取日志（len（a）+ len（b））时间。

假设：input是正确的。 即k在范围[0，len（a）+ len（b）]

基本情况：

• 如果其中一个数组的长度为0，则答案是第二个数组的第k个元素。

还原步骤：

• 如果b中间指数的中间指数小于k
  • 如果a的中间元素大于b中间元素，我们可以忽略b的前半部分，调整k 。
  • 否则忽略a的前半部分，调整k 。
• 否则，如果k小于a和b的中间指数之和：
  • 如果a的中间元素大于b中间元素，我们可以放心地忽略a后半部分
  • 否则我们可以忽略b后半部分

码：

 def kthlargest(arr1, arr2, k): if len(arr1) == 0: return arr2[k] elif len(arr2) == 0: return arr1[k] mida1 = len(arr1)/2 mida2 = len(arr2)/2 if mida1+mida2<k: if arr1[mida1]>arr2[mida2]: return kthlargest(arr1, arr2[mida2+1:], k-mida2-1) else: return kthlargest(arr1[mida1+1:], arr2, k-mida1-1) else: if arr1[mida1]>arr2[mida2]: return kthlargest(arr1[:mida1], arr2, k) else: return kthlargest(arr1, arr2[:mida2], k) 

请注意，我的解决scheme是在每个调用中创build较小数组的新副本，只需在原始数组上传递开始和结束索引即可轻松消除此问题。

Answer 3

许多人回答了这个“从第二个sorting的第k个最小的元素”的问题，但通常只有一般的想法，不是一个明确的工作代码或边界条件分析。

在这里，我想用我的方式仔细阐述它，以帮助一些新手理解我的正确工作的Java代码。 A1和A2是两个按升序排列的数组，分别以size1和size2为长度。 我们需要从这两个数组的联合中find第k个最小的元素。 这里我们合理地假设(k > 0 && k <= size1 + size2) ，这意味着A1和A2不能都是空的。

首先，我们用一个缓慢的O（k）algorithm来处理这个问题。 方法是比较两个数组的第一个元素A1[0]和A2[0] 。 拿小的那个，把A1[0]拿进我们的口袋里。 然后比较A1[1]和A2[0] ，依此类推。 重复这个动作，直到我们的口袋达到k元素。 非常重要：在第一步中，我们只能在口袋里承诺A1[0] 。 我们不能包含或排除A2[0] !!!

下面的O（K）代码在正确的答案之前给你一个元素。 这里我用它来展示我的想法，并分析边界条件。 这个之后我有正确的代码：

 private E kthSmallestSlowWithFault(int k) { int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0; // base case, k == 1 if (k == 1) { if (size1 == 0) { return A2[index2]; } else if (size2 == 0) { return A1[index1]; } else if (A1[index1].compareTo(A2[index2]) < 0) { return A1[index1]; } else { return A2[index2]; } } /* in the next loop, we always assume there is one next element to compare with, so we can * commit to the smaller one. What if the last element is the kth one? */ if (k == size1 + size2) { if (size1 == 0) { return A2[size2 - 1]; } else if (size2 == 0) { return A1[size1 - 1]; } else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) { return A1[size1 - 1]; } else { return A2[size2 - 1]; } } /* * only when k > 1, below loop will execute. In each loop, we commit to one element, till we * reach (index1 + index2 == k - 1) case. But the answer is not correct, always one element * ahead, because we didn't merge base case function into this loop yet. */ int lastElementFromArray = 0; while (index1 + index2 < k - 1) { if (A1[index1].compareTo(A2[index2]) < 0) { index1++; lastElementFromArray = 1; // commit to one element from array A1, but that element is at (index1 - 1)!!! } else { index2++; lastElementFromArray = 2; } } if (lastElementFromArray == 1) { return A1[index1 - 1]; } else { return A2[index2 - 1]; } } 

最强大的想法是，在每个循环中，我们总是使用基本的情况下的方法。 在致力于当前最小元素之后，我们向目标靠近一步：第k个最小元素。 永远不要跳到中间，让自己迷茫和迷失！

通过观察上述代码基础案例k == 1, k == size1+size2 ，并结合A1和A2不能都是空的。 我们可以把逻辑变成更简洁的风格。

这是一个缓慢而正确的工作代码：

 private E kthSmallestSlow(int k) { // System.out.println("this is an O(k) speed algorithm, very concise"); int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0; while (index1 + index2 < k - 1) { if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) { index1++; // here we commit to original index1 element, not the increment one!!! } else { index2++; } } // below is the (index1 + index2 == k - 1) base case // also eliminate the risk of referring to an element outside of index boundary if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } 

现在我们可以尝试一个更快的algorithm运行在O（log k）。 同样，比较A1[k/2]和A2[k/2] ; 如果A1[k/2]较小，则A1[0]至A1[k/2]所有元素都应放在我们的口袋中。 这个想法不仅仅是在每个循环中提交一个元素， 第一步包含k/2元素。 同样，我们也不能包含或排除A2[0]到A2[k/2] 。 所以在第一步中，我们不能超过k/2元素。 第二步，我们不能超过k/4元素。

每一步之后，我们会更接近第k个元素。 同时每一步都越来越小，直到我们到达(step == 1) ，即(k-1 == index1+index2) 。 那么我们可以再次参考简单而强大的基础案例。

这是工作正确的代码：

 private E kthSmallestFast(int k) { // System.out.println("this is an O(log k) speed algorithm with meaningful variables name"); int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0, step = 0; while (index1 + index2 < k - 1) { step = (k - index1 - index2) / 2; int step1 = index1 + step; int step2 = index2 + step; if (size1 > step1 - 1 && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) { index1 = step1; // commit to element at index = step1 - 1 } else { index2 = step2; } } // the base case of (index1 + index2 == k - 1) if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } 

有些人可能会担心如果(index1+index2)跳过k-1？ 我们可以错过基本情况(k-1 == index1+index2)吗？ 这不可能。 你可以加0.5 + 0.25 + 0.125 …，你永远不会超过1。

当然，把上面的代码转换成recursionalgorithm是很容易的：

 private E kthSmallestFastRecur(int k, int index1, int index2, int size1, int size2) { // System.out.println("this is an O(log k) speed algorithm with meaningful variables name"); // the base case of (index1 + index2 == k - 1) if (index1 + index2 == k - 1) { if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } int step = (k - index1 - index2) / 2; int step1 = index1 + step; int step2 = index2 + step; if (size1 > step1 - 1 && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) { index1 = step1; } else { index2 = step2; } return kthSmallestFastRecur(k, index1, index2, size1, size2); } 

希望上面的分析和Java代码可以帮助你理解。 但绝不要复制我的代码作为你的功课！ 干杯;）

Answer 4

下面是@ lambdapilgrim解决scheme的C ++迭代版本（请参阅该algorithm的说明）：

 #include <cassert> #include <iterator> template<class RandomAccessIterator, class Compare> typename std::iterator_traits<RandomAccessIterator>::value_type nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta, RandomAccessIterator firstb, RandomAccessIterator lastb, size_t n, Compare less) { assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less)); for ( ; ; ) { assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb))); if (firsta == lasta) return *(firstb + n); if (firstb == lastb) return *(firsta + n); size_t mida = (lasta - firsta) / 2; size_t midb = (lastb - firstb) / 2; if ((mida + midb) < n) { if (less(*(firstb + midb), *(firsta + mida))) { firstb += (midb + 1); n -= (midb + 1); } else { firsta += (mida + 1); n -= (mida + 1); } } else { if (less(*(firstb + midb), *(firsta + mida))) lasta = (firsta + mida); else lastb = (firstb + midb); } } } 

它适用于所有0 <= n < (size(a) + size(b))索引，并具有O(log(size(a)) + log(size(b)))复杂度。

例

 #include <functional> // greater<> #include <iostream> #define SIZE(a) (sizeof(a) / sizeof(*a)) int main() { int a[] = {5,4,3}; int b[] = {2,1,0}; int k = 1; // find minimum value, the 1st smallest value in a,b int i = k - 1; // convert to zero-based indexing int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b), SIZE(a)+SIZE(b)-1-i, std::greater<int>()); std::cout << v << std::endl; // -> 0 return v; } 

Answer 5

我尝试了第一个k数字，第二个sorting数组中的第k个数字和n个sorting后的数组：

 // require() is recognizable by node.js but not by browser; // for running/debugging in browser, put utils.js and this file in <script> elements, if (typeof require === "function") require("./utils.js"); // Find K largest numbers in two sorted arrays. function k_largest(a, b, c, k) { var sa = a.length; var sb = b.length; if (sa + sb < k) return -1; var i = 0; var j = sa - 1; var m = sb - 1; while (i < k && j >= 0 && m >= 0) { if (a[j] > b[m]) { c[i] = a[j]; i++; j--; } else { c[i] = b[m]; i++; m--; } } debug.log(2, "i: "+ i + ", j: " + j + ", m: " + m); if (i === k) { return 0; } else if (j < 0) { while (i < k) { c[i++] = b[m--]; } } else { while (i < k) c[i++] = a[j--]; } return 0; } // find k-th largest or smallest number in 2 sorted arrays. function kth(a, b, kd, dir){ sa = a.length; sb = b.length; if (kd<1 || sa+sb < kd){ throw "Mission Impossible! I quit!"; } var k; //finding the kd_th largest == finding the smallest k_th; if (dir === 1){ k = kd; } else if (dir === -1){ k = sa + sb - kd + 1;} else throw "Direction has to be 1 (smallest) or -1 (largest)."; return find_kth(a, b, k, sa-1, 0, sb-1, 0); } // find k-th smallest number in 2 sorted arrays; function find_kth(c, d, k, cmax, cmin, dmax, dmin){ sc = cmax-cmin+1; sd = dmax-dmin+1; k0 = k; cmin0 = cmin; dmin0 = dmin; debug.log(2, "=k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin); c_comp = k0-sc; if (c_comp <= 0){ cmax = cmin0 + k0-1; } else { dmin = dmin0 + c_comp-1; k -= c_comp-1; } d_comp = k0-sd; if (d_comp <= 0){ dmax = dmin0 + k0-1; } else { cmin = cmin0 + d_comp-1; k -= d_comp-1; } sc = cmax-cmin+1; sd = dmax-dmin+1; debug.log(2, "#k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin + ", c_comp: " + c_comp + ", d_comp: " + d_comp); if (k===1) return (c[cmin]<d[dmin] ? c[cmin] : d[dmin]); if (k === sc+sd) return (c[cmax]>d[dmax] ? c[cmax] : d[dmax]); m = Math.floor((cmax+cmin)/2); n = Math.floor((dmax+dmin)/2); debug.log(2, "m: " + m + ", n: "+n+", c[m]: "+c[m]+", d[n]: "+d[n]); if (c[m]<d[n]){ if (m === cmax){ // only 1 element in c; return d[dmin+k-1]; } k_next = k-(m-cmin+1); return find_kth(c, d, k_next, cmax, m+1, dmax, dmin); } else { if (n === dmax){ return c[cmin+k-1]; } k_next = k-(n-dmin+1); return find_kth(c, d, k_next, cmax, cmin, dmax, n+1); } } function traverse_at(a, ae, h, l, k, at, worker, wp){ var n = ae ? ae.length : 0; var get_node; switch (at){ case "k": get_node = function(idx){ var node = {}; var pos = l[idx] + Math.floor(k/n) - 1; if (pos<l[idx]){ node.pos = l[idx]; } else if (pos > h[idx]){ node.pos = h[idx];} else{ node.pos = pos; } node.idx = idx; node.val = a[idx][node.pos]; debug.log(6, "pos: "+pos+"\nnode ="); debug.log(6, node); return node; }; break; case "l": get_node = function(idx){ debug.log(6, "a["+idx+"][l["+idx+"]]: "+a[idx][l[idx]]); return a[idx][l[idx]]; }; break; case "h": get_node = function(idx){ debug.log(6, "a["+idx+"][h["+idx+"]]: "+a[idx][h[idx]]); return a[idx][h[idx]]; }; break; case "s": get_node = function(idx){ debug.log(6, "h["+idx+"]-l["+idx+"]+1: "+(h[idx] - l[idx] + 1)); return h[idx] - l[idx] + 1; }; break; default: get_node = function(){ debug.log(1, "!!! Exception: get_node() returns null."); return null; }; break; } worker.init(); debug.log(6, "--* traverse_at() *--"); var i; if (!wp){ for (i=0; i<n; i++){ worker.work(get_node(ae[i])); } } else { for (i=0; i<n; i++){ worker.work(get_node(ae[i]), wp); } } return worker.getResult(); } sumKeeper = function(){ var res = 0; return { init : function(){ res = 0;}, getResult: function(){ debug.log(5, "@@ sumKeeper.getResult: returning: "+res); return res; }, work : function(node){ if (node!==null) res += node;} }; }(); maxPicker = function(){ var res = null; return { init : function(){ res = null;}, getResult: function(){ debug.log(5, "@@ maxPicker.getResult: returning: "+res); return res; }, work : function(node){ if (res === null){ res = node;} else if (node!==null && node > res){ res = node;} } }; }(); minPicker = function(){ var res = null; return { init : function(){ res = null;}, getResult: function(){ debug.log(5, "@@ minPicker.getResult: returning: "); debug.log(5, res); return res; }, work : function(node){ if (res === null && node !== null){ res = node;} else if (node!==null && node.val !==undefined && node.val < res.val){ res = node; } else if (node!==null && node < res){ res = node;} } }; }(); // find k-th smallest number in n sorted arrays; // need to consider the case where some of the subarrays are taken out of the selection; function kth_n(a, ae, k, h, l){ var n = ae.length; debug.log(2, "------** kth_n() **-------"); debug.log(2, "n: " +n+", k: " + k); debug.log(2, "ae: ["+ae+"], len: "+ae.length); debug.log(2, "h: [" + h + "]"); debug.log(2, "l: [" + l + "]"); for (var i=0; i<n; i++){ if (h[ae[i]]-l[ae[i]]+1>k) h[ae[i]]=l[ae[i]]+k-1; } debug.log(3, "--after reduction --"); debug.log(3, "h: [" + h + "]"); debug.log(3, "l: [" + l + "]"); if (n === 1) return a[ae[0]][k-1]; if (k === 1) return traverse_at(a, ae, h, l, k, "l", minPicker); if (k === traverse_at(a, ae, h, l, k, "s", sumKeeper)) return traverse_at(a, ae, h, l, k, "h", maxPicker); var kn = traverse_at(a, ae, h, l, k, "k", minPicker); debug.log(3, "kn: "); debug.log(3, kn); var idx = kn.idx; debug.log(3, "last: k: "+k+", l["+kn.idx+"]: "+l[idx]); k -= kn.pos - l[idx] + 1; l[idx] = kn.pos + 1; debug.log(3, "next: "+"k: "+k+", l["+kn.idx+"]: "+l[idx]); if (h[idx]<l[idx]){ // all elements in a[idx] selected; //remove a[idx] from the arrays. debug.log(4, "All elements selected in a["+idx+"]."); debug.log(5, "last ae: ["+ae+"]"); ae.splice(ae.indexOf(idx), 1); h[idx] = l[idx] = "_"; // For display purpose only. debug.log(5, "next ae: ["+ae+"]"); } return kth_n(a, ae, k, h, l); } function find_kth_in_arrays(a, k){ if (!a || a.length<1 || k<1) throw "Mission Impossible!"; var ae=[], h=[], l=[], n=0, s, ts=0; for (var i=0; i<a.length; i++){ s = a[i] && a[i].length; if (s>0){ ae.push(i); h.push(s-1); l.push(0); ts+=s; } } if (k>ts) throw "Too few elements to choose from!"; return kth_n(a, ae, k, h, l); } ///////////////////////////////////////////////////// // tests // To show everything: use 6. debug.setLevel(1); var a = [2, 3, 5, 7, 89, 223, 225, 667]; var b = [323, 555, 655, 673]; //var b = [99]; var c = []; debug.log(1, "a = (len: " + a.length + ")"); debug.log(1, a); debug.log(1, "b = (len: " + b.length + ")"); debug.log(1, b); for (var k=1; k<a.length+b.length+1; k++){ debug.log(1, "================== k: " + k + "====================="); if (k_largest(a, b, c, k) === 0 ){ debug.log(1, "c = (len: "+c.length+")"); debug.log(1, c); } try{ result = kth(a, b, k, -1); debug.log(1, "===== The " + k + "-th largest number: " + result); } catch (e) { debug.log(0, "Error message from kth(): " + e); } debug.log("=================================================="); } debug.log(1, "################# Now for the n sorted arrays ######################"); debug.log(1, "####################################################################"); x = [[1, 3, 5, 7, 9], [-2, 4, 6, 8, 10, 12], [8, 20, 33, 212, 310, 311, 623], [8], [0, 100, 700], [300], [], null]; debug.log(1, "x = (len: "+x.length+")"); debug.log(1, x); for (var i=0, num=0; i<x.length; i++){ if (x[i]!== null) num += x[i].length; } debug.log(1, "totoal number of elements: "+num); // to test k in specific ranges: var start = 0, end = 25; for (k=start; k<end; k++){ debug.log(1, "=========================== k: " + k + "==========================="); try{ result = find_kth_in_arrays(x, k); debug.log(1, "====== The " + k + "-th smallest number: " + result); } catch (e) { debug.log(1, "Error message from find_kth_in_arrays: " + e); } debug.log(1, "================================================================="); } debug.log(1, "x = (len: "+x.length+")"); debug.log(1, x); debug.log(1, "totoal number of elements: "+num); 

具有debugging使用情况的完整代码可以在以下urlfind： https ： //github.com/brainclone/teasers/tree/master/kth

Answer 6

这是我的基于Jules Olleon解决scheme的代码：

 int getNth(vector<int>& v1, vector<int>& v2, int n) { int step = n / 4; int i1 = n / 2; int i2 = n - i1; while(!(v2[i2] >= v1[i1 - 1] && v1[i1] > v2[i2 - 1])) { if (v1[i1 - 1] >= v2[i2 - 1]) { i1 -= step; i2 += step; } else { i1 += step; i2 -= step; } step /= 2; if (!step) step = 1; } if (v1[i1 - 1] >= v2[i2 - 1]) return v1[i1 - 1]; else return v2[i2 - 1]; } int main() { int a1[] = {1,2,3,4,5,6,7,8,9}; int a2[] = {4,6,8,10,12}; //int a1[] = {1,2,3,4,5,6,7,8,9}; //int a2[] = {4,6,8,10,12}; //int a1[] = {1,7,9,10,30}; //int a2[] = {3,5,8,11}; vector<int> v1(a1, a1+9); vector<int> v2(a2, a2+5); cout << getNth(v1, v2, 5); return 0; } 

Answer 7

这里是我在C中的实现，你可以参考@JulesOlléon对algorithm的解释：algorithm背后的思想是我们维护i + j = k，并且find这样的i和j，使得[i-1] <b [j-1] <a [i]（或者相反）。 现在，由于a中小于b [j-1]的i个元素和小于b [j-1]的b中的j-1个元素，所以b [j-1]是i + j-1 + 1 =第k个最小元素。 为了find这样的i，jalgorithm在数组上进行二分search。

 int find_k(int A[], int m, int B[], int n, int k) { if (m <= 0 )return B[k-1]; else if (n <= 0) return A[k-1]; int i = ( m/double (m + n)) * (k-1); if (i < m-1 && i<k-1) ++i; int j = k - 1 - i; int Ai_1 = (i > 0) ? A[i-1] : INT_MIN, Ai = (i<m)?A[i]:INT_MAX; int Bj_1 = (j > 0) ? B[j-1] : INT_MIN, Bj = (j<n)?B[j]:INT_MAX; if (Ai >= Bj_1 && Ai <= Bj) { return Ai; } else if (Bj >= Ai_1 && Bj <= Ai) { return Bj; } if (Ai < Bj_1) { // the answer can't be within A[0,...,i] return find_k(A+i+1, mi-1, B, n, j); } else { // the answer can't be within A[0,...,i] return find_k(A, m, B+j+1, nj-1, i); } } 

Answer 8

这是我的解决scheme。 C ++代码使用循环打印第k个最小值和迭代次数以获得第k个最小值，在我看来，这个循环的次序是log（k）。 但是代码要求k小于第一个数组的长度，这是一个限制。

 #include <iostream> #include <vector> #include<math.h> using namespace std; template<typename comparable> comparable kthSmallest(vector<comparable> & a, vector<comparable> & b, int k){ int idx1; // Index in the first array a int idx2; // Index in the second array b comparable maxVal, minValPlus; float iter = k; int numIterations = 0; if(k > a.size()){ // Checks if k is larger than the size of first array cout << " k is larger than the first array" << endl; return -1; } else{ // If all conditions are satisfied, initialize the indexes idx1 = k - 1; idx2 = -1; } for ( ; ; ){ numIterations ++; if(idx2 == -1 || b[idx2] <= a[idx1] ){ maxVal = a[idx1]; minValPlus = b[idx2 + 1]; idx1 = idx1 - ceil(iter/2); // Binary search idx2 = k - idx1 - 2; // Ensures sum of indices = k - 2 } else{ maxVal = b[idx2]; minValPlus = a[idx1 + 1]; idx2 = idx2 - ceil(iter/2); // Binary search idx1 = k - idx2 - 2; // Ensures sum of indices = k - 2 } if(minValPlus >= maxVal){ // Check if kth smallest value has been found cout << "The number of iterations to find the " << k << "(th) smallest value is " << numIterations << endl; return maxVal; } else iter/=2; // Reduce search space of binary search } } int main(){ //Test Cases vector<int> a = {2, 4, 9, 15, 22, 34, 45, 55, 62, 67, 78, 85}; vector<int> b = {1, 3, 6, 8, 11, 13, 15, 20, 56, 67, 89}; // Input k < a.size() int kthSmallestVal; for (int k = 1; k <= a.size() ; k++){ kthSmallestVal = kthSmallest<int>( a ,b ,k ); cout << k <<" (th) smallest Value is " << kthSmallestVal << endl << endl << endl; } } 

Answer 9

检查这个代码。

 import math def findkthsmallest(): A=[1,5,10,22,30,35,75,125,150,175,200] B=[15,16,20,22,25,30,100,155,160,170] lM=0 lN=0 hM=len(A)-1 hN=len(B)-1 k=17 while True: if k==1: return min(A[lM],B[lN]) cM=hM-lM+1 cN=hN-lN+1 tmp = cM/float(cM+cN) iM=int(math.ceil(tmp*k)) iN=k-iM iM=lM+iM-1 iN=lN+iN-1 if A[iM] >= B[iN]: if iN == hN or A[iM] < B[iN+1]: return A[iM] else: k = k - (iN-lN+1) lN=iN+1 hM=iM-1 if B[iN] >= A[iM]: if iM == hM or B[iN] < A[iM+1]: return B[iN] else: k = k - (iM-lM+1) lM=iM+1 hN=iN-1 if hM < lM: return B[lN+k-1] if hN < lN: return A[lM+k-1] if __name__ == '__main__': print findkthsmallest(); 

Answer 10

上面提供的第一个伪代码不适用于许多值。 例如，这里有两个数组。 int [] a = {1，5，6，8，9，11，15，17，19}; int [] b = {4，7，8，13，15，18，20，24，26};

它不适用于k = 3和k = 9。 我有另一个解决scheme。 它在下面给出。

 private static void traverse(int pt, int len) { int temp = 0; if (len == 1) { int val = 0; while (k - (pt + 1) - 1 > -1 && M[pt] < N[k - (pt + 1) - 1]) { if (val == 0) val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; else { int t = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; val = val < t ? val : t; } ++pt; } if (val == 0) val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; System.out.println(val); return; } temp = len / 2; if (M[pt + temp - 1] < N[k - (pt + temp) - 1]) { traverse(pt + temp, temp); } else { traverse(pt, temp); } } 

但是…它也不适用于k = 5。 这是偶然的/奇怪的k不让它简单。

Answer 11

 public class KthSmallestInSortedArray { public static void main(String[] args) { int a1[] = {2, 3, 10, 11, 43, 56}, a2[] = {120, 13, 14, 24, 34, 36}, k = 4; System.out.println(findKthElement(a1, a2, k)); } private static int findKthElement(int a1[], int a2[], int k) { /** Checking k must less than sum of length of both array **/ if (a1.length + a2.length < k) { throw new IllegalArgumentException(); } /** K must be greater than zero **/ if (k <= 0) { throw new IllegalArgumentException(); } /** * Finding begin, l and end such that * begin <= l < end * a1[0].....a1[l-1] and * a2[0]....a2[kl-1] are the smallest k numbers */ int begin = Math.max(0, k - a2.length); int end = Math.min(a1.length, k); while (begin < end) { int l = begin + (end - begin) / 2; /** Can we include a1[l] in the k smallest numbers */ if ((l < a1.length) && (k - l > 0) && (a1[l] < a2[k - l - 1])) { begin = l + 1; } else if ((l > 0) && (k - l < a2.length) && (a1[l - 1] > a2[k - 1])) { /** * This is the case where we can discard * a[l-1] from the set of k smallest numbers */ end = l; } else { /** * We found our answer since both inequalities were * false */ begin = l; break; } } if (begin == 0) { return a2[k - 1]; } else if (begin == k) { return a1[k - 1]; } else { return Math.max(a1[begin - 1], a2[k - begin - 1]); } } } 

Answer 12

这是我在java中的解决scheme。 将尝试进一步优化它

  public class FindKLargestTwoSortedArray { public static void main(String[] args) { int[] arr1 = { 10, 20, 40, 80 }; int[] arr2 = { 15, 35, 50, 75 }; FindKLargestTwoSortedArray(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, 6); } public static void FindKLargestTwoSortedArray(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2, int k) { if ((start1 <= end1 && start1 >= 0 && end1 < arr1.length) && (start2 <= end2 && start2 >= 0 && end2 < arr2.length)) { int midIndex1 = (start1 + (k - 1) / 2); midIndex1 = midIndex1 >= arr1.length ? arr1.length - 1 : midIndex1; int midIndex2 = (start2 + (k - 1) / 2); midIndex2 = midIndex2 >= arr2.length ? arr2.length - 1 : midIndex2; if (arr1[midIndex1] == arr2[midIndex2]) { System.out.println("element is " + arr1[midIndex1]); } else if (arr1[midIndex1] < arr2[midIndex2]) { if (k == 1) { System.out.println("element is " + arr1[midIndex1]); return; } else if (k == 2) { System.out.println("element is " + arr2[midIndex2]); return; }else if (midIndex1 == arr1.length-1 || midIndex2 == arr2.length-1 ) { if(k==(arr1.length+arr2.length)){ System.out.println("element is " + arr2[midIndex2]); return; }else if(k==(arr1.length+arr2.length)-1){ System.out.println("element is " + arr1[midIndex1]); return; } } int remainingElementToSearch = k - (midIndex1-start1); FindKLargestTwoSortedArray( arr1, midIndex1, (midIndex1 + remainingElementToSearch) >= arr1.length ? arr1.length-1 : (midIndex1 + remainingElementToSearch), arr2, start2, midIndex2, remainingElementToSearch); } else if (arr1[midIndex1] > arr2[midIndex2]) { FindKLargestTwoSortedArray(arr2, start2, end2, arr1, start1, end1, k); } } else { return; } } } 

这是灵感来自Algo在精彩的YouTubevideo

Answer 13

链接到代码复杂性（log（n）+ log（m））

链接到代码 （log（n）* log（m））

（log（n）+ log（m））解决scheme的实现

我想补充一下我的解释。 这是一个经典的问题，我们必须使用这两个数组sorting的事实。 我们给出了两个大小为sz1和arr2大小为sz2的sorting数组arr1

a）让我们假设如果

检查k是否有效

k是>（sz1 + sz2）

那么我们不能在两个有序数组的联合中find第k个最小元素。因此返回无效的数据。 b）现在，如果上述条件成立，我们有有效和可行的k值，

pipe理边缘案例

我们将在前面添加-infinity值，在末尾添加+ infinity值，以覆盖k = 1,2和k =（sz1 + sz2-1），（sz1 + sz2）等边缘情况。

现在这两个数组的大小分别为（sz1 + 2）和（sz2 + 2）

主algorithm

现在，我们将在arr1上进行二分search。我们将在arr1上进行二分search，查找索引i， startIndex <= i <= endIndex

这样如果我们使用约束{（i + j）= k}在arr2中find相应的索引j，那么如果

如果（arr2 [j-1] <arr1 [i] <arr2 [j]） ，则arr1 [i]是第k小（情况1）

否则如果（arr1 [i-1] <arr2 [j] <arr1 [i]） ，则arr2 [i]是第k个最小的（情况2）

否则表示arr1 [i] <arr2 [j-1] <arr2 [j] （Case3）

或者arr2 [j-1] <arr2 [j] <arr1 [i] （Case4）

既然我们知道第k个最小的元素在两个数组ryt的并集中有（k-1）个元素小于它 ？ 所以，

在Case1中，我们确保arr1 [i]的元素总数小于（k-1）个小元素，因为arr1数组中比arr1 [i]小的元素数量比我们知道的数目是i-1（arr2 [ j-1] < arr1[i] < arr2[j]) and number of elements smaller than arr1[i] in arr2 is j-1 because j is found using (i-1)+(j-1) = (k -1) So kth smallest element will be arr1[i]

But answer may not always come from the first array ie arr1 so we checked for case2 which also satisfies similarly like case 1 because (i-1)+(j-1) = (k-1) . Now if we have (arr1[i-1] < arr2[j] < arr1[i]) we have a total of k-1 elements smaller than arr2[j] in union of both the arrays so its the kth smallest element.

In case3 , to form it to any of case 1 or case 2, we need to increment i and j will be found according using constraint {(i+j) = k} ie in binary search move to right part ie make startIndex = middleIndex

In case4 , to form it to any of case 1 or case 2, we need to decrement i and j will be found according using constraint {(i+j) = k} ie in binary search move to left part ie make endIndex = middleIndex.

Now how to decide startIndex and endIndex at beginning of binary search over arr1 with startindex = 1 and endIndex = ??.We need to decide.

If k > sz1,endIndex = (sz1+1) , else endIndex = k;

Because if k is greater than the size of the first array we may have to do binary search over the entire array arr1 else we only need to take first k elements of it because sz1-k elements can never contribute in calculating kth smallest.

CODE Shown Below

 // Complexity O(log(n)+log(m)) #include<bits/stdc++.h> using namespace std; #define f(i,x,y) for(int i = (x);i < (y);++i) #define F(i,x,y) for(int i = (x);i > (y);--i) int max(int a,int b){return (a > b?a:b);} int min(int a,int b){return (a < b?a:b);} int mod(int a){return (a > 0?a:((-1)*(a)));} #define INF 1000000 int func(int *arr1,int *arr2,int sz1,int sz2,int k) { if((k <= (sz1+sz2))&&(k > 0)) { int s = 1,e,i,j; if(k > sz1)e = sz1+1; else e = k; while((es)>1) { i = (e+s)/2; j = ((k-1)-(i-1)); j++; if(j > (sz2+1)){s = i;} else if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i]; else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j]; else if(arr1[i] < arr2[j-1]){s = i;} else if(arr1[i] > arr2[j]){e = i;} else {;} } i = e,j = ((k-1)-(i-1));j++; if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i]; else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j]; else { i = s,j = ((k-1)-(i-1));j++; if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i]; else return arr2[j]; } } else { cout << "Data Invalid" << endl; return -INF; } } int main() { int n,m,k; cin >> n >> m >> k; int arr1[n+2]; int arr2[m+2]; f(i,1,n+1) cin >> arr1[i]; f(i,1,m+1) cin >> arr2[i]; arr1[0] = -INF; arr2[0] = -INF; arr1[n+1] = +INF; arr2[m+1] = +INF; int val = func(arr1,arr2,n,m,k); if(val != -INF)cout << val << endl; return 0; } 

For Solution of complexity (log(n)*log(m))

Just i missed using advantage of the fact that for each i the j can be found using constraint {(i-1)+(j-1)=(k-1)} So for each ii was further applying binary search on second array to find j such that arr2[j] <= arr1[i].So this solution can be optimized further

Answer 14

Basically, via this approach you can discard k/2 elements at each step. The K will recursively change from k => k/2 => k/4 => … till it reaches 1. So, Time Complexity is O(logk)

At k=1 , we get the lowest of the two arrays.

The following code is in JAVA. Please note that the we are subtracting 1 (-1) in the code from the indices because Java array's index starts from 0 and not 1, eg. k=3 is represented by the element in 2nd index of an array.

 private int kthElement(int[] arr1, int[] arr2, int k) { if (k < 1 || k > (arr1.length + arr2.length)) return -1; return helper(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k); } private int helper(int[] arr1, int low1, int high1, int[] arr2, int low2, int high2, int k) { if (low1 > high1) { return arr2[low2 + k - 1]; } else if (low2 > high2) { return arr1[low1 + k - 1]; } if (k == 1) { return Math.min(arr1[low1], arr2[low2]); } int i = Math.min(low1 + k / 2, high1 + 1); int j = Math.min(low2 + k / 2, high2 + 1); if (arr1[i - 1] > arr2[j - 1]) { return helper(arr1, low1, high1, arr2, j, high2, k - (j - low2)); } else { return helper(arr1, i, high1, arr2, low2, high2, k - (i - low1)); } } 

Answer 15

Below C# code to Find the k-th Smallest Element in the Union of Two Sorted Arrays. Time Complexity : O(logk)

  public static int findKthSmallestElement1(int[] A, int startA, int endA, int[] B, int startB, int endB, int k) { int n = endA - startA; int m = endB - startB; if (n <= 0) return B[startB + k - 1]; if (m <= 0) return A[startA + k - 1]; if (k == 1) return A[startA] < B[startB] ? A[startA] : B[startB]; int midA = (startA + endA) / 2; int midB = (startB + endB) / 2; if (A[midA] <= B[midB]) { if (n / 2 + m / 2 + 1 >= k) return findKthSmallestElement1(A, startA, endA, B, startB, midB, k); else return findKthSmallestElement1(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1); } else { if (n / 2 + m / 2 + 1 >= k) return findKthSmallestElement1(A, startA, midA, B, startB, endB, k); else return findKthSmallestElement1(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1); } }