Dadas dos arrays ordenadas de tamaño m y n respectivamente, tiene la tarea de encontrar el elemento que estaría en la k-ésima posición de la array ordenada final.
Ejemplos:
Input : Array 1 - 2 3 6 7 9
Array 2 - 1 4 8 10
k = 5
Output : 6
Explanation: The final sorted array would be -
1, 2, 3, 4, 6, 7, 8, 9, 10
The 5th element of this array is 6.
Input : Array 1 - 100 112 256 349 770
Array 2 - 72 86 113 119 265 445 892
k = 7
Output : 256
Explanation: Final sorted array is -
72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892
7th element of this array is 256.
Enfoque básico
Dado que tenemos dos arrays ordenadas, podemos usar la técnica de fusión para obtener la array fusionada final. A partir de esto, simplemente vamos al índice k’th.
C++
// Program to find kth element from two sorted arrays
#include <iostream>
using namespace std;
int kth(int arr1[], int arr2[], int m, int n, int k)
{
int sorted1[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}
// Driver Code
int main()
{
int arr1[5] = {2, 3, 6, 7, 9};
int arr2[4] = {1, 4, 8, 10};
int k = 5;
cout << kth(arr1, arr2, 5, 4, k);
return 0;
}
Java
// Java Program to find kth element
// from two sorted arrays
class Main
{
static int kth(int arr1[], int arr2[], int m, int n, int k)
{
int[] sorted1 = new int[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n)
{
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}
// Driver Code
public static void main (String[] args)
{
int arr1[] = {2, 3, 6, 7, 9};
int arr2[] = {1, 4, 8, 10};
int k = 5;
System.out.print(kth(arr1, arr2, 5, 4, k));
}
}
/* This code is contributed by Harsh Agarwal */
Python3
# Program to find kth element # from two sorted arrays def kth(arr1, arr2, m, n, k): sorted1 = [0] * (m + n) i = 0 j = 0 d = 0 while (i < m and j < n): if (arr1[i] < arr2[j]): sorted1[d] = arr1[i] i += 1 else: sorted1[d] = arr2[j] j += 1 d += 1 while (i < m): sorted1[d] = arr1[i] d += 1 i += 1 while (j < n): sorted1[d] = arr2[j] d += 1 j += 1 return sorted1[k - 1] # Driver code arr1 = [2, 3, 6, 7, 9] arr2 = [1, 4, 8, 10] k = 5 print(kth(arr1, arr2, 5, 4, k)) # This code is contributed by Smitha Dinesh Semwal
C#
// C# Program to find kth element
// from two sorted arrays
class GFG {
static int kth(int[] arr1, int[] arr2, int m, int n,
int k)
{
int[] sorted1 = new int[m + n];
int i = 0, j = 0, d = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}
// Driver Code
static void Main()
{
int[] arr1 = { 2, 3, 6, 7, 9 };
int[] arr2 = { 1, 4, 8, 10 };
int k = 5;
System.Console.WriteLine(kth(arr1, arr2, 5, 4, k));
}
}
// This code is contributed by mits
PHP
<?php
// Program to find kth
// element from two
// sorted arrays
function kth($arr1, $arr2,
$m, $n, $k)
{
$sorted1[$m + $n] = 0;
$i = 0;
$j = 0;
$d = 0;
while ($i < $m && $j < $n)
{
if ($arr1[$i] < $arr2[$j])
$sorted1[$d++] = $arr1[$i++];
else
$sorted1[$d++] = $arr2[$j++];
}
while ($i < $m)
$sorted1[$d++] = $arr1[$i++];
while ($j < $n)
$sorted1[$d++] = $arr2[$j++];
return $sorted1[$k - 1];
}
// Driver Code
$arr1 = array(2, 3, 6, 7, 9);
$arr2 = array(1, 4, 8, 10);
$k = 5;
echo kth($arr1, $arr2, 5, 4, $k);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// JavaScript Program to find kth element
// from two sorted arrays
function kth(arr1 , arr2 , m , n , k) {
var sorted1 = Array(m + n).fill(0);
var i = 0, j = 0, d = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
sorted1[d++] = arr1[i++];
else
sorted1[d++] = arr2[j++];
}
while (i < m)
sorted1[d++] = arr1[i++];
while (j < n)
sorted1[d++] = arr2[j++];
return sorted1[k - 1];
}
// Driver Code
var arr1 = [ 2, 3, 6, 7, 9 ];
var arr2 = [ 1, 4, 8, 10 ];
var k = 5;
document.write(kth(arr1, arr2, 5, 4, k));
// This code contributed by umadevi9616
</script>
Producción
6
Complejidad temporal: O(n)
Espacio auxiliar: O(m + n)
Versión optimizada para el espacio del enfoque anterior: podemos evitar el uso de una array adicional.
C++
// C++ program to find kth element
// from two sorted arrays
#include <bits/stdc++.h>
using namespace std;
int find(int A[], int B[], int m,
int n, int k_req)
{
int k = 0, i = 0, j = 0;
// Keep taking smaller of the current
// elements of two sorted arrays and
// keep incrementing k
while(i < m && j < n)
{
if(A[i] < B[j])
{
k++;
if(k == k_req)
return A[i];
i++;
}
else
{
k++;
if(k == k_req)
return B[j];
j++;
}
}
// If array B[] is completely traversed
while(i < m)
{
k++;
if(k == k_req)
return A[i];
i++;
}
// If array A[] is completely traversed
while(j < n)
{
k++;
if(k == k_req)
return B[j];
j++;
}
}
// Driver Code
int main()
{
int A[5] = { 2, 3, 6, 7, 9 };
int B[4] = { 1, 4, 8, 10 };
int k = 5;
cout << find(A, B, 5, 4, k);
return 0;
}
// This code is contributed by Sreejith S
Java
import java.io.*;
class GFG {
public static int find(int A[], int B[], int m, int n,
int k_req)
{
int k = 0, i = 0, j = 0;
// Keep taking smaller of the current
// elements of two sorted arrays and
// keep incrementing k
while (i < m && j < n) {
if (A[i] < B[j]) {
k++;
if (k == k_req)
return A[i];
i++;
}
else {
k++;
if (k == k_req)
return B[j];
j++;
}
}
// If array B[] is completely traversed
while (i < m) {
k++;
if (k == k_req)
return A[i];
i++;
}
// If array A[] is completely traversed
while (j < n) {
k++;
if (k == k_req)
return B[j];
j++;
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 2, 3, 6, 7, 9 };
int[] B = { 1, 4, 8, 10 };
int k = 5;
System.out.println(find(A, B, 5, 4, k));
}
}
Python3
# Python3 Program to find kth element # from two sorted arrays def find(A, B, m, n, k_req): i, j, k = 0, 0, 0 # Keep taking smaller of the current # elements of two sorted arrays and # keep incrementing k while i < len(A) and j < len(B): if A[i] < B[j]: k += 1 if k == k_req: return A[i] i += 1 else: k += 1 if k == k_req: return B[j] j += 1 # If array B[] is completely traversed while i < len(A): k += 1 if k == k_req: return A[i] i += 1 # If array A[] is completely traversed while j < len(B): k += 1 if k == k_req: return B[j] j += 1 # driver code A = [2, 3, 6, 7, 9] B = [1, 4, 8, 10] k = 5; print(find(A, B, 5, 4, k)) # time complexity of O(k)
C#
// C# program to find kth element
// from two sorted arrays
using System;
public class GFG
{
public static int find(int[] A, int[] B,
int m, int n,int k_req)
{
int k = 0, i = 0, j = 0;
// Keep taking smaller of the current
// elements of two sorted arrays and
// keep incrementing k
while (i < m && j < n) {
if (A[i] < B[j]) {
k++;
if (k == k_req)
return A[i];
i++;
}
else {
k++;
if (k == k_req)
return B[j];
j++;
}
}
// If array B[] is completely traversed
while (i < m)
{
k++;
if (k == k_req)
return A[i];
i++;
}
// If array A[] is completely traversed
while (j < n)
{
k++;
if (k == k_req)
return B[j];
j++;
}
return -1;
}
// Driver Code
static public void Main (){
int[] A = { 2, 3, 6, 7, 9 };
int[] B = { 1, 4, 8, 10 };
int k = 5;
Console.WriteLine(find(A, B, 5, 4, k));
}
}
// This code is contributed by rag2127
Javascript
<script>
function find(A, B, m, n, k_req)
{
let k = 0, i = 0, j = 0;
// Keep taking smaller of the current
// elements of two sorted arrays and
// keep incrementing k
while (i < m && j < n) {
if (A[i] < B[j]) {
k++;
if (k == k_req)
return A[i];
i++;
}
else {
k++;
if (k == k_req)
return B[j];
j++;
}
}
// If array B[] is completely traversed
while (i < m) {
k++;
if (k == k_req)
return A[i];
i++;
}
// If array A[] is completely traversed
while (j < n) {
k++;
if (k == k_req)
return B[j];
j++;
}
return -1;
}
// Driver Code
let A = [ 2, 3, 6, 7, 9 ];
let B = [ 1, 4, 8, 10 ];
let k = 5;
document.write(find(A, B, 5, 4, k));
// This code is contributed by Dharanendra L V.
</script>
Producción
6
Complejidad temporal: O(k)
Espacio auxiliar: O(1)
- Enfoque Divide y vencerás 1
Si bien el método anterior funciona, ¿podemos hacer que nuestro algoritmo sea más eficiente? La respuesta es sí. Mediante el uso de un enfoque de divide y vencerás, similar al que se usa en la búsqueda binaria, podemos intentar encontrar el k’ésimo elemento de una manera más eficiente. - Compare los elementos intermedios de las arrays arr1 y arr2, llamemos a estos índices mid1 y mid2 respectivamente. Supongamos arr1[mid1] k, entonces claramente los elementos después de mid2 no pueden ser el elemento requerido. Establezca el último elemento de arr2 para que sea arr2[mid2].
- De esta manera, defina un nuevo subproblema con la mitad del tamaño de una de las arrays.
C++
// Program to find k-th element from two sorted arrays
#include <iostream>
using namespace std;
int kth(int *arr1, int *arr2, int *end1, int *end2, int k)
{
if (arr1 == end1)
return arr2[k];
if (arr2 == end2)
return arr1[k];
int mid1 = (end1 - arr1) / 2;
int mid2 = (end2 - arr2) / 2;
if (mid1 + mid2 < k)
{
if (arr1[mid1] > arr2[mid2])
return kth(arr1, arr2 + mid2 + 1, end1, end2,
k - mid2 - 1);
else
return kth(arr1 + mid1 + 1, arr2, end1, end2,
k - mid1 - 1);
}
else
{
if (arr1[mid1] > arr2[mid2])
return kth(arr1, arr2, arr1 + mid1, end2, k);
else
return kth(arr1, arr2, end1, arr2 + mid2, k);
}
}
int main()
{
int arr1[5] = {2, 3, 6, 7, 9};
int arr2[4] = {1, 4, 8, 10};
int k = 5;
cout << kth(arr1, arr2, arr1 + 5, arr2 + 4, k - 1);
return 0;
}
Python3
# Python program to find k-th element from two sorted arrays def kth(arr1, arr2, n, m, k): if n == 1 or m == 1: if m == 1: arr2, arr1 = arr1, arr2 m = n if k == 1: return min(arr1[0], arr2[0]) elif k == m + 1: return max(arr1[0], arr2[0]) else: if arr2[k - 1] < arr1[0]: return arr2[k - 1] else: return max(arr1[0], arr2[k - 2]) mid1 = (n - 1)//2 mid2 = (m - 1)//2 if mid1+mid2+1 < k: if arr1[mid1] < arr2[mid2]: return kth(arr1[mid1 + 1:], arr2, n - mid1 - 1, m, k - mid1 - 1) else: return kth(arr1, arr2[mid2 + 1:], n, m - mid2 - 1, k - mid2 - 1) else: if arr1[mid1] < arr2[mid2]: return kth(arr1, arr2[:mid2 + 1], n, mid2 + 1, k) else: return kth(arr1[:mid1 + 1], arr2, mid1 + 1, m, k) if __name__ == "__main__": arr1 = [2, 3, 6, 7, 9] arr2 = [1, 4, 8, 10] k = 5 print(kth(arr1, arr2, 5, 4, k)) # This code is contributed by harshitkap00r
Producción
6
Tenga en cuenta que en el código anterior, k es 0 indexado, lo que significa que si queremos que ak sea 1 indexado, tenemos que restar 1 al pasarlo a la función.
Complejidad de tiempo: O (log n + log m)
Espacio Auxiliar: O(logn + logm)
Enfoque de divide y vencerás 2
Si bien la implementación anterior es muy eficiente, aún podemos hacerla más eficiente. En lugar de dividir la array en segmentos de n / 2 y m / 2 y luego recurrir, podemos dividirlos por k / 2 y repetir. La siguiente implementación muestra esto.
Explanation: Instead of comparing the middle element of the arrays, we compare the k / 2nd element. Let arr1 and arr2 be the arrays. Now, if arr1[k / 2] arr1[1] New subproblem: Array 1 - 6 7 9 Array 2 - 1 4 8 10 k = 5 - 2 = 3 floor(k / 2) = 1 arr1[1] = 6 arr2[1] = 1 arr1[1] > arr2[1] New subproblem: Array 1 - 6 7 9 Array 2 - 4 8 10 k = 3 - 1 = 2 floor(k / 2) = 1 arr1[1] = 6 arr2[1] = 4 arr1[1] > arr2[1] New subproblem: Array 1 - 6 7 9 Array 2 - 8 10 k = 2 - 1 = 1 Now, we directly compare first elements, since k = 1. arr1[1] < arr2[1] Hence, arr1[1] = 6 is the answer.
C++
// C++ Program to find kth element from two sorted arrays
#include <iostream>
using namespace std;
int kth(int arr1[], int arr2[], int m, int n, int k,
int st1 = 0, int st2 = 0)
{
// In case we have reached end of array 1
if (st1 == m)
return arr2[st2 + k - 1];
// In case we have reached end of array 2
if (st2 == n)
return arr1[st1 + k - 1];
// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
return -1;
// Compare first elements of arrays and return
if (k == 1)
return (arr1[st1] < arr2[st2]) ?
arr1[st1] : arr2[st2];
int curr = k / 2;
// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{
// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
return arr2[st2 + (k - (m - st1) - 1)];
else
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
// Size of array 2 is less than k / 2
if (curr-1 >= n-st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
return arr1[st1 + (k - (n - st2) - 1)];
else
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
else
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}
// Driver code
int main()
{
int arr1[5] = {2, 3, 6, 7, 9};
int arr2[4] = {1, 4, 8, 10};
int k = 5;
cout << kth(arr1, arr2, 5, 4, k);
return 0;
}
Java
// Java Program to find kth element from two sorted arrays
class GFG
{
static int kth(int arr1[], int arr2[], int m,
int n, int k, int st1, int st2)
{
// In case we have reached end of array 1
if (st1 == m)
{
return arr2[st2 + k - 1];
}
// In case we have reached end of array 2
if (st2 == n)
{
return arr1[st1 + k - 1];
}
// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
{
return -1;
}
// Compare first elements of arrays and return
if (k == 1)
{
return (arr1[st1] < arr2[st2])
? arr1[st1] : arr2[st2];
}
int curr = k / 2;
// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{
// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
{
return arr2[st2 + (k - (m - st1) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}
// Size of array 2 is less than k / 2
if (curr - 1 >= n - st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
{
return arr1[st1 + (k - (n - st2) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
}
else
// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}
// Driver code
public static void main(String[] args)
{
int arr1[] = {2, 3, 6, 7, 9};
int arr2[] = {1, 4, 8, 10};
int k = 5;
int st1 = 0, st2 = 0;
System.out.println(kth(arr1, arr2, 5, 4, k, st1, st2));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find kth element from # two sorted arrays def kth(arr1, arr2, m, n, k, st1 = 0, st2 = 0): # In case we have reached end of array 1 if (st1 == m): return arr2[st2 + k - 1] # In case we have reached end of array 2 if (st2 == n): return arr1[st1 + k - 1] # k should never reach 0 or exceed sizes # of arrays if (k == 0 or k > (m - st1) + (n - st2)): return -1 # Compare first elements of arrays and return if (k == 1): if(arr1[st1] < arr2[st2]): return arr1[st1] else: return arr2[st2] curr = int(k / 2) # Size of array 1 is less than k / 2 if(curr - 1 >= m - st1): # Last element of array 1 is not kth # We can directly return the (k - m)th # element in array 2 if (arr1[m - 1] < arr2[st2 + curr - 1]): return arr2[st2 + (k - (m - st1) - 1)] else: return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr) # Size of array 2 is less than k / 2 if (curr - 1 >= n - st2): if (arr2[n - 1] < arr1[st1 + curr - 1]): return arr1[st1 + (k - (n - st2) - 1)] else: return kth(arr1, arr2, m, n, k - curr,st1 + curr, st2) else: # Normal comparison, move starting index # of one array k / 2 to the right if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]): return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2) else: return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr) # Driver code arr1 = [ 2, 3, 6, 7, 9 ] arr2 = [ 1, 4, 8, 10 ] k = 5 print(kth(arr1, arr2, 5, 4, k)) # This code is contributed by avanitrachhadiya2155
C#
// C# Program to find kth element from two sorted arrays
using System;
class GFG
{
static int kth(int []arr1, int []arr2, int m,
int n, int k, int st1, int st2)
{
// In case we have reached end of array 1
if (st1 == m)
{
return arr2[st2 + k - 1];
}
// In case we have reached end of array 2
if (st2 == n)
{
return arr1[st1 + k - 1];
}
// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2))
{
return -1;
}
// Compare first elements of arrays and return
if (k == 1)
{
return (arr1[st1] < arr2[st2])
? arr1[st1] : arr2[st2];
}
int curr = k / 2;
// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1)
{
// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1])
{
return arr2[st2 + (k - (m - st1) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}
// Size of array 2 is less than k / 2
if (curr - 1 >= n - st2)
{
if (arr2[n - 1] < arr1[st1 + curr - 1])
{
return arr1[st1 + (k - (n - st2) - 1)];
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
}
else
// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
{
return kth(arr1, arr2, m, n, k - curr,
st1 + curr, st2);
}
else
{
return kth(arr1, arr2, m, n, k - curr,
st1, st2 + curr);
}
}
// Driver code
public static void Main(String[] args)
{
int []arr1 = {2, 3, 6, 7, 9};
int []arr2 = {1, 4, 8, 10};
int k = 5;
int st1 = 0, st2 = 0;
Console.WriteLine(kth(arr1, arr2, 5, 4, k, st1, st2));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript Program to find kth element from two sorted arrays
function kth(arr1 , arr2 , m , n , k , st1 , st2)
{
// In case we have reached end of array 1
if (st1 == m) {
return arr2[st2 + k - 1];
}
// In case we have reached end of array 2
if (st2 == n) {
return arr1[st1 + k - 1];
}
// k should never reach 0 or exceed sizes
// of arrays
if (k == 0 || k > (m - st1) + (n - st2)) {
return -1;
}
// Compare first elements of arrays and return
if (k == 1) {
return (arr1[st1] < arr2[st2]) ? arr1[st1] : arr2[st2];
}
var curr = parseInt(k / 2);
// Size of array 1 is less than k / 2
if (curr - 1 >= m - st1) {
// Last element of array 1 is not kth
// We can directly return the (k - m)th
// element in array 2
if (arr1[m - 1] < arr2[st2 + curr - 1]) {
return arr2[st2 + (k - (m - st1) - 1)];
} else {
return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);
}
}
// Size of array 2 is less than k / 2
if (curr - 1 >= n - st2) {
if (arr2[n - 1] < arr1[st1 + curr - 1]) {
return arr1[st1 + (k - (n - st2) - 1)];
} else {
return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);
}
} else
// Normal comparison, move starting index
// of one array k / 2 to the right
if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]) {
return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);
} else {
return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);
}
}
// Driver code
var arr1 = [ 2, 3, 6, 7, 9 ];
var arr2 = [ 1, 4, 8, 10 ];
var k = 5;
var st1 = 0, st2 = 0;
document.write(kth(arr1, arr2, 5, 4, k, st1, st2));
// This code is contributed by gauravrajput1
</script>
Producción
6
Complejidad del tiempo: O(log k)
Espacio Auxiliar: O(logk)
Ahora, k puede tomar un valor máximo de m + n. Esto significa que log k puede ser, en el peor de los casos, log(m + n). Logm + logn = log(mn) por las propiedades de los logaritmos, y cuando m, n > 2, log(m + n) < log(mn). Por lo tanto, este algoritmo supera ligeramente al algoritmo anterior. Además, vea otro enfoque log k simple implementado sugerido por Raj Kumar.
C++
// C++ Program to find kth
// element from two sorted arrays
// Time Complexity: O(log k)
#include <iostream>
using namespace std;
int kth(int arr1[], int m, int arr2[], int n, int k)
{
if (k > (m + n) || k < 1)
return -1;
// let m <= n
if (m > n)
return kth(arr2, n, arr1, m, k);
// Check if arr1 is empty returning
// k-th element of arr2
if (m == 0)
return arr2[k - 1];
// Check if k = 1 return minimum of
// first two elements of both
// arrays
if (k == 1)
return min(arr1[0], arr2[0]);
// Now the divide and conquer part
int i = min(m, k / 2), j = min(n, k / 2);
if (arr1[i - 1] > arr2[j - 1])
// Now we need to find only
// k-j th element since we
// have found out the lowest j
return kth(arr1, m, arr2 + j, n - j, k - j);
else
// Now we need to find only
// k-i th element since we
// have found out the lowest i
return kth(arr1 + i, m - i, arr2, n, k - i);
}
// Driver code
int main()
{
int arr1[5] = { 2, 3, 6, 7, 9 };
int arr2[4] = { 1, 4, 8, 10 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
int k = 5;
int ans = kth(arr1, m, arr2, n, k);
if (ans == -1)
cout << "Invalid query";
else
cout << ans;
return 0;
}
// This code is contributed by Raj Kumar
Java
// Java Program to find kth element
// from two sorted arrays
// Time Complexity: O(log k)
import java.util.Arrays;
class Gfg {
static int kth(int arr1[], int m, int arr2[], int n,
int k)
{
if (k > (m + n) || k < 1)
return -1;
// let m > n
if (m > n)
return kth(arr2, n, arr1, m, k);
// Check if arr1 is empty returning
// k-th element of arr2
if (m == 0)
return arr2[k - 1];
// Check if k = 1 return minimum of first
// two elements of both arrays
if (k == 1)
return Math.min(arr1[0], arr2[0]);
// Now the divide and conquer part
int i = Math.min(m, k / 2);
int j = Math.min(n, k / 2);
if (arr1[i - 1] > arr2[j - 1]) {
// Now we need to find only k-j th element
// since we have found out the lowest j
int temp[] = Arrays.copyOfRange(arr2, j, n);
return kth(arr1, m, temp, n - j, k - j);
}
// Now we need to find only k-i th element
// since we have found out the lowest i
int temp[] = Arrays.copyOfRange(arr1, i, m);
return kth(temp, m - i, arr2, n, k - i);
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 2, 3, 6, 7, 9 };
int arr2[] = { 1, 4, 8, 10 };
int m = arr1.length;
int n = arr2.length;
int k = 5;
int ans = kth(arr1, m, arr2, n, k);
if (ans == -1)
System.out.println("Invalid query");
else
System.out.println(ans);
}
}
// This code is contributed by Vivek Kumar Singh
Python3
# Python3 Program to find kth element from two
# sorted arrays. Time Complexity: O(log k)
def kth(arr1, m, arr2, n, k):
if (k > (m + n) or k < 1):
return -1
# Let m <= n
if (m > n):
return kth(arr2, n, arr1, m, k)
# Check if arr1 is empty returning
# k-th element of arr2
if (m == 0):
return arr2[k - 1]
# Check if k = 1 return minimum of
# first two elements of both
# arrays
if (k == 1):
return min(arr1[0], arr2[0])
# Now the divide and conquer part
i = min(m, k // 2)
j = min(n, k // 2)
if (arr1[i - 1] > arr2[j - 1]):
# Now we need to find only
# k-j th element since we
# have found out the lowest j
return kth(arr1, m, arr2[j:], n - j, k - j)
else:
# Now we need to find only
# k-i th element since we
# have found out the lowest i
return kth(arr1[i:], m - i, arr2, n, k - i)
# Driver code
arr1 = [ 2, 3, 6, 7, 9 ]
arr2 = [ 1, 4, 8, 10 ]
m = len(arr1)
n = len(arr2)
k = 5
ans = kth(arr1, m, arr2, n, k)
if (ans == -1):
print("Invalid query")
else:
print(ans)
# This code is contributed by Shubham Singh
C#
// C# Program to find kth element
// from two sorted arrays
// Time Complexity: O(log k)
using System;
using System.Collections.Generic;
public class GFG{
static int kth(int[] arr1, int m, int[] arr2, int n,
int k)
{
if (k > (m + n) || k < 1)
return -1;
// let m > n
if (m > n)
return kth(arr2, n, arr1, m, k);
// Check if arr1 is empty returning
// k-th element of arr2
if (m == 0)
return arr2[k - 1];
// Check if k = 1 return minimum of first
// two elements of both arrays
if (k == 1)
return Math.Min(arr1[0], arr2[0]);
// Now the divide and conquer part
int i = Math.Min(m, k / 2);
int j = Math.Min(n, k / 2);
if (arr1[i - 1] > arr2[j - 1]) {
// Now we need to find only k-j th element
// since we have found out the lowest j
int[] temp = new int[n - j];
Array.Copy(arr2, j, temp, 0, n-j);
return kth(arr1, m, temp, n - j, k - j);
}
// Now we need to find only k-i th element
// since we have found out the lowest i
int[] temp1 = new int[m-i];
Array.Copy(arr1, i, temp1, 0, m-i);
return kth(temp1, m - i, arr2, n, k - i);
}
// Driver code
public static void Main()
{
int[] arr1 = { 2, 3, 6, 7, 9 };
int[] arr2 = { 1, 4, 8, 10 };
int m = arr1.Length;
int n = arr2.Length;
int k = 5;
int ans = kth(arr1, m, arr2, n, k);
if (ans == -1)
Console.WriteLine("Invalid query");
else
Console.WriteLine(ans);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript program to illustrate time
// complexity for Nested loops
function kth(arr1, m, arr2, n, k)
{
if (k > (m + n) || k < 1){
return -1;
}
// let m <= n
if (m > n){
return kth(arr2, n, arr1, m, k);
}
// Check if arr1 is empty returning
// k-th element of arr2
if (m == 0){
return arr2[k - 1];
}
// Check if k = 1 return minimum of
// first two elements of both
// arrays
if (k == 1){
return Math.min(arr1[0], arr2[0]);
}
// Now the divide and conquer part
let i = Math.min(m, parseInt(k / 2));
let j = Math.min(n, parseInt(k / 2));
if (arr1[i - 1] > arr2[j - 1]){
// Now we need to find only
// k-j th element since we
// have found out the lowest j
let temp = arr2.slice(j,n)
return kth(arr1, m, temp, n - j, k - j);
}
else{
// Now we need to find only
// k-i th element since we
// have found out the lowest i
let temp = arr1.slice(i,m)
return kth( temp, m - i, arr2, n, k - i);
}
}
// Driver code
let arr1 = [ 2, 3, 6, 7, 9 ];
let arr2 = [ 1, 4, 8, 10 ];
let m = 5;
let n = 4;
let k = 5;
let ans = kth(arr1, m, arr2, n, k);
if (ans == -1){
document.write("Invalid query");
}
else{
document.write(ans);
}
// This code is contributed by Shubham Singh
</script>
Producción
6
Complejidad del tiempo: O(log k)
Espacio Auxiliar: O(log k)
Otro enfoque: (Usando Min Heap)
- Empuje los elementos de ambas arrays a una cola de prioridad (min-heap).
- Elementos k-1 desplegables desde el frente.
- El elemento al frente de la cola de prioridad es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find kth
// element from two sorted arrays
#include <bits/stdc++.h>
using namespace std;
// Function to find K-th min
int kth(int* a, int* b, int n, int m, int k)
{
// Declaring a min heap
priority_queue<int, vector<int>,
greater<int> > pq;
// Pushing elements for
// array a to min-heap
for (int i = 0; i < n; i++) {
pq.push(a[i]);
}
// Pushing elements for
// array b to min-heap
for (int i = 0; i < m; i++) {
pq.push(b[i]);
}
// Popping-out K-1 elements
while (k-- > 1) {
pq.pop();
}
return pq.top();
}
//Driver Code
int main()
{
int arr1[5] = {2, 3, 6, 7, 9};
int arr2[4] = {1, 4, 8, 10};
int k = 5;
cout << kth(arr1, arr2, 5, 4, k);
return 0;
}
// This code is contributed by yashbeersingh42
Java
// Java Program to find kth element
// from two sorted arrays
import java.util.*;
class GFG {
// Function to find K-th min
static int kth(int a[], int b[],
int n, int m, int k)
{
// Declaring a min heap
PriorityQueue<Integer> pq =
new PriorityQueue<>();
// Pushing elements for
// array a to min-heap
for (int i = 0; i < n; i++) {
pq.offer(a[i]);
}
// Pushing elements for
// array b to min-heap
for (int i = 0; i < m; i++) {
pq.offer(b[i]);
}
// Popping-out K-1 elements
while (k-- > 1) {
pq.remove();
}
return pq.peek();
}
// Driver Code
public static void main(String[] args)
{
int arr1[] = { 2, 3, 6, 7, 9 };
int arr2[] = { 1, 4, 8, 10 };
int k = 5;
System.out.print(kth(arr1, arr2, 5, 4, k));
}
}
// This code is contributed by yashbeersingh42
Python3
# Python Program to find kth element # from two sorted arrays # Function to find K-th min def kth(a , b , n , m , k): # Declaring a min heap pq = []; # Pushing elements for # array a to min-heap for i in range(n): pq.append(a[i]); # Pushing elements for # array b to min-heap for i in range(m): pq.append(b[i]); pq = sorted(pq, reverse = True) # Popping-out K-1 elements while (k > 1): k -= 1; pq.pop(); return pq.pop(); # Driver Code arr1 = [ 2, 3, 6, 7, 9 ]; arr2 = [ 1, 4, 8, 10 ]; k = 5; print(kth(arr1, arr2, 5, 4, k)); # This code is contributed by Saurabh Jaiswal
C#
// C# Program to find kth element
// from two sorted arrays
using System;
using System.Collections.Generic;
public class GFG {
// Function to find K-th min
static int kth(int []a, int []b, int n, int m, int k) {
// Declaring a min heap
List<int> pq = new List<int>();
// Pushing elements for
// array a to min-heap
for (int i = 0; i < n; i++) {
pq.Add(a[i]);
}
// Pushing elements for
// array b to min-heap
for (int i = 0; i < m; i++) {
pq.Add(b[i]);
}
pq.Sort();
// Popping-out K-1 elements
while (k-- > 1) {
pq.RemoveAt(0);
}
return pq[0];
}
// Driver Code
public static void Main(String[] args) {
int []arr1 = { 2, 3, 6, 7, 9 };
int []arr2 = { 1, 4, 8, 10 };
int k = 5;
Console.Write(kth(arr1, arr2, 5, 4, k));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript Program to find kth element
// from two sorted arrays
// Function to find K-th min
function kth(a , b , n , m , k) {
// Declaring a min heap
var pq = [];
// Pushing elements for
// array a to min-heap
for (i = 0; i < n; i++) {
pq.push(a[i]);
}
// Pushing elements for
// array b to min-heap
for (i = 0; i < m; i++) {
pq.push(b[i]);
}
pq.sort((a,b)=>b-a);
// Popping-out K-1 elements
while (k-- > 1) {
pq.pop();
}
return pq.pop();
}
// Driver Code
var arr1 = [ 2, 3, 6, 7, 9 ];
var arr2 = [ 1, 4, 8, 10 ];
var k = 5;
document.write(kth(arr1, arr2, 5, 4, k));
// This code is contributed by gauravrajput1
</script>
Producción
6
Complejidad de tiempo: O (NlogN)
Espacio Auxiliar: O(m+n)
Otro enfoque: (Usando Upper Bound STL)
Dadas dos arrays ordenadas de tamaño m y n respectivamente, tiene la tarea de encontrar el elemento que estaría en la k-ésima posición de la array ordenada final.
Ejemplos:
Entrada: Array 1 – 2 3 6 7 9
Array 2 – 1 4 8 10
k = 5
Salida : 6
Explicación: la array ordenada final sería:
1, 2, 3, 4, 6, 7, 8, 9, 10
El quinto elemento de esta array es 6. El primer elemento de esta array es 1. Lo que hay que notar aquí es que upper_bound(6) da 5, upper_bound(4) da 4, que es un número de elemento igual o menor que el número que están dando como entrada a upper_bound().
Aquí hay otro ejemplo
Entrada: Array 1 – 100 112 256 349 770
Array 2 – 72 86 113 119 265 445 892
k = 7
Salida : 256
Explicación: la array ordenada final es:
72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892
El séptimo elemento de esta array es 256.
Observación requerida:
El método más simple para resolver esta pregunta es usar upper_bound para verificar cuál es la posición de un elemento en la array ordenada. La función upper_bound devuelve el puntero al elemento que es mayor que el elemento que buscamos.
Entonces, para encontrar el k-ésimo elemento, solo necesitamos encontrar el elemento cuyo límite superior() es 4. Entonces, nuevamente, ahora que sabemos lo que nos da el límite superior(), necesitamos 1 última observación para resolver esta pregunta. Si nos han dado 2 arrays, solo necesitamos la suma de upper_bound para las 2 arrays
Entrada: Array 1 – 2 3 6 7 9
Array 2 – 1 4 8 10
k = 5
El valor de upper_bound para el valor (6) en la array 1 es 3 y para la array 2 es 2. Esto nos da un total de 5, que es la respuesta.
Algoritmo:
- Tomamos un medio entre [L,R] usando la fórmula mid = (L+R)/2.
- Compruebe si el medio puede ser el k-ésimo elemento usando la función upper_bound()
- Encuentre la suma de upper_bound() para ambas arrays y si la suma es >= K, es un valor posible del k-ésimo elemento.
- Si sum es >= K entonces asignamos R = mid – 1.
- de lo contrario, si suma <k, entonces el valor medio actual es demasiado pequeño y asignamos L = medio+1.
- Repetir desde arriba
- Devuelve el valor más pequeño encontrado.
Aquí está la implementación para el método optimizado:
C++
// C++ program to find the kth element
#include <bits/stdc++.h>
using namespace std;
long long int maxN
= 1e10; // the maximum value in the array possible.
long long int kthElement(int arr1[], int arr2[], int n,
int m, int k)
{
long long int left = 1,
right
= maxN; // The range of where ans can lie.
long long int ans = 1e15; // We have to find min of all
// the ans so take .
// using binary search to check all possible values of
// kth element
while (left <= right) {
long long int mid = (left + right) / 2;
long long int up_cnt
= upper_bound(arr1, arr1 + n, mid) - arr1;
up_cnt += upper_bound(arr2, arr2 + m, mid) - arr2;
if (up_cnt >= k) {
ans = min(ans,
mid); // find the min of all answers.
right
= mid - 1; // Try to find a smaller answer.
}
else
left = mid + 1; // Current mid is too small so
// shift right.
}
return ans;
}
// Driver code
int main()
{
// Example 1
int n = 5, m = 7, k = 7;
int arr1[n] = { 100, 112, 256, 349, 770 };
int arr2[m] = { 72, 86, 113, 119, 265, 445, 892 };
cout << kthElement(arr1, arr2, n, m, k) << endl;
return 0;
}
Java
// Java program to find the kth element
import java.util.*;
class GFG{
static long maxN = (long)1e10; // the maximum value in the array possible.
static int upperBound(int[] a, int low,
int high, long element)
{
while(low < high){
int middle = low + (high - low)/2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
static long kthElement(int arr1[], int arr2[], int n,
int m, int k)
{
long left = 1, right = maxN; // The range of where ans can lie.
long ans = (long)1e15; // We have to find min of all
// the ans so take .
// using binary search to check all possible values of
// kth element
while (left <= right) {
long mid = (left + right) / 2;
long up_cnt = upperBound(arr1,0, n, mid);
up_cnt += upperBound(arr2, 0, m, mid);
if (up_cnt >= k) {
ans = Math.min(ans,
mid); // find the min of all answers.
right
= mid - 1; // Try to find a smaller answer.
}
else
left = mid + 1; // Current mid is too small so
// shift right.
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// Example 1
int n = 5, m = 7, k = 7;
int arr1[] = { 100, 112, 256, 349, 770 };
int arr2[] = { 72, 86, 113, 119, 265, 445, 892 };
System.out.print(kthElement(arr1, arr2, n, m, k) +"\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python program to find the kth element maxN = 10**10 # the maximum value in the array possible. def upperBound(a, low, high, element): while(low < high): middle = low + (high - low)//2 if(a[middle] > element): high = middle else: low = middle + 1 return low def kthElement(arr1, arr2, n, m, k): left = 1 right = maxN # The range of where ans can lie. ans = 10**15 # We have to find min of all # the ans so take . # using binary search to check all possible values of # kth element while (left <= right): mid = (left + right) // 2 up_cnt = upperBound(arr1,0, n, mid) up_cnt += upperBound(arr2, 0, m, mid) if (up_cnt >= k): ans = min(ans, mid) # find the min of all answers. right= mid - 1 # Try to find a smaller answer. else: left = mid + 1 # Current mid is too small so # shift right. return ans # Driver code # Example 1 n = 5 m = 7 k = 7 arr1 = [100, 112, 256, 349, 770] arr2 = [72, 86, 113, 119, 265, 445, 892] print(kthElement(arr1, arr2, n, m, k)) # This code is contributed by Shubham Singh
C#
// C# program to find the kth element
using System;
public class GFG{
static long maxN = (long)1e10; // the maximum value in the array possible.
static int upperBound(int[] a, int low,
int high, long element)
{
while(low < high){
int middle = low + (high - low)/2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
static long kthElement(int[] arr1, int[] arr2, int n,
int m, int k)
{
long left = 1, right = maxN; // The range of where ans can lie.
long ans = (long)1e15; // We have to find min of all
// the ans so take .
// using binary search to check all possible values of
// kth element
while (left <= right) {
long mid = (left + right) / 2;
long up_cnt = upperBound(arr1,0, n, mid);
up_cnt += upperBound(arr2, 0, m, mid);
if (up_cnt >= k) {
ans = Math.Min(ans,
mid); // find the min of all answers.
right
= mid - 1; // Try to find a smaller answer.
}
else
left = mid + 1; // Current mid is too small so
// shift right.
}
return ans;
}
// Driver code
static public void Main (){
// Example 1
int n = 5, m = 7, k = 7;
int[] arr1 = { 100, 112, 256, 349, 770 };
int[] arr2 = { 72, 86, 113, 119, 265, 445, 892 };
Console.Write(kthElement(arr1, arr2, n, m, k) +"\n");
}
}
// This code is contributed by SHubham Singh
Javascript
<script>
// Javascript program to find the kth element
var maxN = 10000000000; // the maximum value in the array possible.
function upperBound(a, low, high, element)
{
while(low < high){
var middle = parseInt(low + (high - low)/2);
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
function kthElement(arr1, arr2, n, m, k)
{
var left = 1
var right = maxN; // The range of where ans can lie.
var ans = 1000000000000000; // We have to find min of all
// the ans so take .
// using binary search to check all possible values of
// kth element
while (left <= right) {
var mid = parseInt((left + right) / 2);
var up_cnt = upperBound(arr1,0, n, mid);
up_cnt += upperBound(arr2, 0, m, mid);
if (up_cnt >= k) {
ans = Math.min(ans,
mid); // find the min of all answers.
right
= mid - 1; // Try to find a smaller answer.
}
else
left = mid + 1; // Current mid is too small so
// shift right.
}
return ans;
}
// Driver code
// Example 1
var n = 5, m = 7, k = 7;
var arr1 = [ 100, 112, 256, 349, 770 ];
var arr2 = [ 72, 86, 113, 119, 265, 445, 892 ];
document.write(kthElement(arr1, arr2, n, m, k));
// This code is contributed by Shubham Singh
</script>
Producción
256
Complejidad de tiempo : O( Log( maxN ).log( N+M ) )
Espacio auxiliar : O( 1 )
Este artículo es una contribución de Aditya Kamath . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA