كيف تجد أصغر عنصر KTH في اتحاد صفيفتين فرزتين؟
https://stackoverflow.com/questions/4607945
-
25-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هذا هو سؤال الواجب المنزلي. يقولون أن الأمر يتطلب O(logN + logM) أين N و M هي أطوال المصفوفات.
دعونا نسمي المصفوفات a و b. من الواضح أننا يمكن أن نتجاهل الجميع a[i] و b[i] أين أنا> ك.
أولا دعونا نقارن a[k/2] و b[k/2]. يترك b[k/2] > a[k/2]. لذلك يمكننا تجاهل كل شيء b[i], ، حيث أنا> k/2.
الآن لدينا كل شيء a[i], ، حيث أنا <k وجميع b[i], ، حيث أنا <k/2 للعثور على الإجابة.
ما هي الخطوة التالية؟
المحلول
لقد حصلت عليه ، فقط استمر! وكن حذرًا مع الفهارس ...
لتبسيط قليلاً ، سأفترض أن 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]
من أجل العرض التوضيحي ، يمكنك استخدام Loop Instariant I + J = K ، لكنني لن أقوم بكل واجبك المنزلي :)
نصائح أخرى
آمل ألا أجيب على واجبك المنزلي كما كان أكثر من عام منذ طرح هذا السؤال. فيما يلي حل عودية ذيل سيستغرق وقت السجل (Len (a)+len (b)).
الافتراض: المدخلات صحيحة. IE K في النطاق [0 ، Len (a)+len (b)
الحالات الأساسية:
- إذا كان طول إحدى المصفوفات 0 ، فإن الإجابة هي العنصر KTH من الصفيف الثاني.
خطوات التخفيض:
- إذا كان فهرس منتصف
a+ فهرس منتصف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)
يرجى ملاحظة أن الحل الخاص بي هو إنشاء نسخ جديدة من المصفوفات الأصغر في كل مكالمة ، ويمكن القضاء عليها بسهولة من خلال تمرير المؤشرات الناشئة والنهاية على المصفوفات الأصلية.
أجاب العديد من الأشخاص على هذا "أصغر عنصر من العناصر من صفيفين فرزتين" ، ولكن عادةً مع الأفكار العامة فقط ، وليس رمز عمل واضح أو تحليل شروط الحدود.
أرغب هنا في توضيح ذلك بعناية بالطريقة التي ذهبت بها على الرغم من مساعدة بعض المبتدئين على فهمها ، مع رمز Java الصحيح الخاص بي. A1 و A2 هما صفان تصاعديان فرزان ، مع size1 و size2 كما الطول على التوالي. نحتاج إلى العثور على عنصر K-Th الأصغر من اتحاد هاتين المصفمين. هنا نفترض ذلك بشكل معقول (k > 0 && k <= size1 + size2), ، مما يعني أن A1 و A2 لا يمكن أن تكون فارغة.
أولاً ، دعنا نتعامل مع هذا السؤال مع خوارزمية بطيئة O (K). الطريقة هي مقارنة العنصر الأول من كلا الصفيف ، 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-Th. لا تقفز أبدًا إلى الوسط وتجعل نفسك مرتبكًا وفقدت!
من خلال مراقبة حالة قاعدة الكود أعلاه 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];
}
}
الآن يمكننا تجربة خوارزمية أسرع تعمل عند 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-Th. في الوقت نفسه ، تصبح كل خطوة أصغر وأصغر ، حتى نصل (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.
بالطبع ، من السهل جدًا تحويل الكود أعلاه إلى خوارزمية عودية:
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 على الفهم. ولكن لا تنسخ رمزك كواجبك المنزلي! هتافات ؛)
إليك نسخة تكرارية C ++ من @Lambdapilgrim حل (انظر شرح الخوارزمية هناك):
#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;
}
محاولتي لأرقام K الأولى ، رقم KTH في صفيفتين فرزتين ، وفي المصفوفات المفرزة:
// 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);
يمكن العثور على الرمز الكامل مع utils تصحيح الأخطاء على: https://github.com/brainclone/teasers/tree/master/kth
إليكم رمزتي على أساس حل جول أولون:
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;
}
إليكم تنفيذي في C ، يمكنك الرجوع إلى @Jules Olléon يشرح للخوارزمية: الفكرة وراء الخوارزمية هي أننا نحافظ <b [j-1] <a [i] (أو العكس جولة). الآن نظرًا لوجود عناصر I في "A" أصغر من B [J-1] ، وعناصر J-1 في "B" أصغر من B [J-1] ، B [J-1] هي I + J-1 + 1 = KTH أصغر عنصر. للعثور على مثل هذه ، تقوم j الخوارزمية بإجراء بحث ثنائي التثبيت على المصفوفات.
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, m-i-1, B, n, j);
} else { // the answer can't be within A[0,...,i]
return find_k(A, m, B+j+1, n-j-1, i);
}
}
هذا هو الحل. يقوم رمز C ++ بطباعة قيمة KTH الأصغر وكذلك عدد التكرارات للحصول على أصغر قيمة KTH باستخدام حلقة ، والتي في رأيي هي في ترتيب السجل (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;
}
}
لا يعمل الرمز الزائف الأول المذكور أعلاه ، ولا يعمل للعديد من القيم. على سبيل المثال ، إليك صفيفان. 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 في ذلك. لدي حل آخر. ويرد أدناه.
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 الذي لا يسمح له أن يكون بسيطًا.
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[k-l-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]);
}
}
}
هنا حل الألغام في جافا. سيحاول تحسينه
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 في فيديو يوتيوب رائع
رابط إلى الكود التعقيد (سجل (ن)+سجل (م))
رابط إلى الكود (log (n)*log (m))
التنفيذ حل (سجل (ن)+سجل (م))
أود أن أضيف توضيحي إلى المشكلة. هذه مشكلة كلاسيكية حيث يتعين علينا استخدام حقيقة أن الصيفين يتم فرزهما. لقد حصلنا على صفيفتين فرزتين ARR1 من Size SZ1 و ARR2 بحجم SZ2
أ) لنفترض إذا
التحقق مما إذا كان K صالحًا
K هو> (SZ1+SZ2)
بعد ذلك ، لا يمكننا العثور على أصغر KTH في الاتحاد من كلا المصفوفات المصنفة RYT ، لذا أعد بيانات غير صالحة. ب) الآن إذا كانت الشرط أعلاه خاطئًا وكان لدينا قيمة صالحة ومجدية لـ K ،
إدارة حالات الحافة
سنقوم بإلحاق كل من المصفوفات بواسطة قيم -infinity في الأمام و+لا نهاية لها في النهاية لتغطية حالات الحافة K = 1،2 و K = (SZ1+SZ2-1) ، (SZ1+SZ2) وما إلى ذلك.
الآن كلا المصفمين لها حجم (SZ1+2) و (SZ2+2) على التوالى
الخوارزمية الرئيسية
الآن ، سنقوم بالبحث الثنائي على ARR1. سنقوم بالبحث الثنائي على ARR1 نبحث عن فهرس I ، startIndex <= i <= endIndex
بحيث وجدنا الفهرس المقابل J في ARR2 باستخدام القيد {(i+j) = k} ، إذا
لو (ARR2 [J-1] <arr1 [i] <arr2 [j])، ثم arr1 [i] هو أصغر KTH (الحالة 1)
آخر إذا (ARR1 [I-1] <arr2 [j] <arr1 [i]) ، ثم arr2 [i] هو أصغر KTH (الحالة 2)
آخر يدل على أيضا arr1 [i] <arr2 [j-1] <arr2 [j (Case3)
أو ARR2 [J-1] <arr2 [j] <arr1 [i (Case4)
لأننا نعلم أن KTH أصغر عنصر لديه عناصر (K-1) أصغر منه في اتحاد كل من المصفمين RYT؟ لذا،
في حالة 1, ، ما فعلناه ، لقد تأكدنا أن هناك ما مجموعه (K-1) عناصر أصغر لـ ARR1 [i] لأن العناصر الأصغر من ARR1 [i] في Arr1 Array هي I-1 في العدد مما نعرفه (ARR2 [J- 1] <arr1 [i] <arr2 [j]) وعدد العناصر الأصغر من Arr1 [i] في Arr2 هو J-1 لأنه تم العثور على J باستخدام (I-1)+(J-1) = (K-1 ) لذلك سيكون kth أصغر عنصر arr1 [i
لكن الإجابة قد لا تأتي دائمًا من المصفوفة الأولى IE ARR1 لذلك قمنا بتسجيل الدخول Case2 الذي يرضي أيضًا بالمثل مثل الحالة 1 لأن (I-1)+(J-1) = (K-1). الآن إذا كان لدينا (ARR1 [I-1] <arr2 [j] <arr1 [i]) ، فلدينا ما مجموعه عناصر K-1 أصغر من ARR2 [J] في اتحاد كل من الصفيفتين ، لذا فإن عنصر KTH الأصغر.
في Case3 ، لتشكيلها في أي من الحالة 1 أو الحالة 2 ، نحتاج إلى زيادة I و J وفقًا لاستخدام القيد {(i+j) = k} IE في حركة البحث الثنائي إلى الجزء الأيمن ، أي جعل startIndex = middleindex
في Case4, ، لتشكيله على أي من الحالة 1 أو الحالة 2 ، نحتاج إلى انخفاض I و J وفقًا لاستخدام القيد {(i+j) = k} في نقل الثنائي إلى الجزء الأيسر ، أي جعل endindex = middleindex.
الآن كيف تقرر startIndex و EndIndex في بداية البحث الثنائي عبر ARR1 مع startIndex = 1 و EndIndex =؟
إذا كان k> sz1 ، endindex = (sz1+1) ، else endindex = k ؛
لأنه إذا كان K أكبر من حجم الصفيف الأول ، فقد يتعين علينا إجراء بحث ثنائي على Array Arr1 بأكمله ، نحتاج فقط إلى أخذ عناصر K الأولى منه لأن عناصر SZ1-K لا يمكن أن تسهم أبدًا في حساب KTH الأصغر.
الكود الموضح أدناه
// 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((e-s)>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;
}
لحل التعقيد (سجل (n)*log (m))
فقط فاتني استخدام ميزة حقيقة أنه يمكن العثور على j لكل I {(I-1)+(j-1) = (k-1)} ، لذلك تم تطبيق البحث الثنائي على كل II على الصفيف الثاني للعثور على j بحيث يمكن تحسين ARR2 [j] <= arr1 [i]. لذلك يمكن تحسين هذا الحل
في الأساس ، من خلال هذا النهج ، يمكنك تجاهل عناصر K/2 في كل خطوة. سوف يتغير K بشكل متكرر من K => K/2 => K/4 => ... حتى يصل إلى 1.لذلك ، تعقيد الوقت س (logk)
عند k = 1 ، نحصل على أدنى صفيف.
الكود التالي في جافا. يرجى ملاحظة أن نحن نطرح 1 (-1) في الكود من المؤشرات لأن فهرس جافا صفيف يبدأ من 0 وليس 1 ، على سبيل المثال. k = 3 يمثل العنصر في الفهرس الثاني من مجموعة.
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));
}
}
#include <bits/stdc++.h>
using namespace std;
int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){
if(start1 >= end1)return b[start2+k-1];
if(start2 >= end2)return a[start1+k-1];
if(k==1)return min(a[start1],b[start2]);
int aMax = INT_MAX;
int bMax = INT_MAX;
if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1];
if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1];
if(aMax > bMax){
return findKthElement(a,start1,end1,b,start2+k/2,end2,k-k/2);
}
else{
return findKthElement(a,start1 + k/2,end1,b,start2,end2,k-k/2);
}
}
int main(void){
int t;
scanf("%d",&t);
while(t--){
int n,m,k;
cout<<"Enter the size of 1st Array"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the Element of 1st Array"<<endl;
for(int i = 0;i<n;i++){
cin>>arr[i];
}
cout<<"Enter the size of 2nd Array"<<endl;
cin>>m;
int arr1[m];
cout<<"Enter the Element of 2nd Array"<<endl;
for(int i = 0;i<m;i++){
cin>>arr1[i];
}
cout<<"Enter The Value of K";
cin>>k;
sort(arr,arr+n);
sort(arr1,arr1+m);
cout<<findKthElement(arr,0,n,arr1,0,m,k)<<endl;
}
return 0;
}
Time Complexcity هو O (log (min (n ، m)))
تحقق من هذا الرمز.
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();
أدناه C# رمز للعثور على أصغر عنصر K-Th في الاتحاد من اثنين من المصفوفات المصنفة. تعقيد الوقت: 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);
}
}
