Dada una array ordenada arr[] de tamaño N y un número entero K , la tarea es encontrar el elemento más pequeño presente en la array. La array dada se obtuvo invirtiendo las subarreglas {arr[0], arr[R]} y {arr[R + 1], arr[N – 1]} en algún índice aleatorio R. Si la clave no está presente en el array, imprime -1 .
Ejemplos:
Entrada: arr[] = { 4, 3, 2, 1, 8, 7, 6, 5 }, K = 2
Salida: 2
Explicación: la forma ordenada de la array arr[] es { 1, 2, 3, 4, 5, 6, 7, 8}. Por lo tanto, el segundo elemento más pequeño de la array arr[] es 2.Entrada: arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 }, K = 3
Salida: 5
Enfoque ingenuo: el enfoque más simple para resolver el problema es ordenar la array dada arr[] en orden creciente e imprimir el K -ésimo elemento más pequeño de la array.
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Enfoque alternativo de la solución anterior: podemos ordenar la array sin usar ninguna técnica de clasificación que seguramente reducirá la complejidad del tiempo. Podemos simplemente encontrar el punto de pivote P en la array (alrededor del cual ocurre la rotación) usando la búsqueda binaria y simplemente invertir las dos subarreglas [0, P + 1] y [P + 1, N] usando la función std::reverse() en C++.
Inversión de los subarreglos: después de encontrar el punto de pivote P , simplemente encuentre el reverso de los dos subarreglos de la siguiente manera:
std::reverse(arr, arr + P + 1);
std::reverse(arr + P + 1, arr + N);
Y así obtenemos la array ordenada y podemos imprimir el K- ésimo elemento más pequeño como arr[K-1] .
C++
// C++ program for the above approach.
#include <bits/stdc++.h>
using namespace std;
/* Function to get pivot. For array 4, 3, 2, 1, 6, 5
it returns 3 (index of 1) */
int findPivot(int arr[], int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (mid < high && arr[mid] < arr[mid + 1])
return mid;
if (mid > low && arr[mid] > arr[mid - 1])
return (mid - 1);
if (arr[low] <= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
// Function Call
int P = findPivot(arr, 0, N - 1);
// reversing first subarray
reverse(arr, arr + P + 1);
// reversing second subarray
reverse(arr + P + 1, arr + N);
// printing output
cout << arr[K - 1];
return 0;
}
// This code is contributed by Pranjay Vats
Java
// Java program for the above approach.
import java.util.*;
class GFG{
// Function to get pivot. For array 4, 3, 2, 1, 6, 5
// it returns 3 (index of 1)
static int findPivot(int arr[], int low, int high)
{
// Base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (mid < high && arr[mid] < arr[mid + 1])
return mid;
if (mid > low && arr[mid] > arr[mid - 1])
return (mid - 1);
if (arr[low] <= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
static void reverse(int str[], int start, int end)
{
// Temporary variable to store character
int temp;
while (start <= end)
{
// Swapping the first and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 };
int N = arr.length;
int K = 3;
// Function Call
int P = findPivot(arr, 0, N - 1);
// Reversing first subarray
reverse(arr, 0, P);
// Reversing second subarray
reverse(arr, P, N - 1);
// Printing output
System.out.print(arr[K - 1]);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach. # Function to get pivot. For array 4, 3, 2, 1, 6, 5 # it returns 3 (index of 1) def findPivot(arr, low, high): # Base cases if (high < low): return -1 if (high == low): return low mid = int((low + high) / 2) #low + (high - low)/2; if (mid < high and arr[mid] < arr[mid + 1]): return mid if (mid > low and arr[mid] > arr[mid - 1]): return (mid - 1) if (arr[low] <= arr[mid]): return findPivot(arr, low, mid - 1) return findPivot(arr, mid + 1, high) def reverse(Str, start, end): while (start <= end): # Swapping the first and last character temp = Str[start] Str[start] = Str[end] Str[end] = temp start+=1 end-=1 # Given Input arr = [ 10, 8, 6, 5, 2, 1, 13, 12 ] N = len(arr) K = 3 # Function Call P = findPivot(arr, 0, N - 1) # Reversing first subarray reverse(arr, 0, P) # Reversing second subarray reverse(arr, P, N - 1) # Printing output print(arr[K - 1]) # This code is contributed by decode2207.
C#
// C# program for the above approach.
using System;
class GFG {
// Function to get pivot. For array 4, 3, 2, 1, 6, 5
// it returns 3 (index of 1)
static int findPivot(int[] arr, int low, int high)
{
// Base cases
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (mid < high && arr[mid] < arr[mid + 1])
return mid;
if (mid > low && arr[mid] > arr[mid - 1])
return (mid - 1);
if (arr[low] <= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
static void reverse(int[] str, int start, int end)
{
// Temporary variable to store character
int temp;
while (start <= end)
{
// Swapping the first and last character
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
static void Main() {
// Given Input
int[] arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
int N = arr.Length;
int K = 3;
// Function Call
int P = findPivot(arr, 0, N - 1);
// Reversing first subarray
reverse(arr, 0, P);
// Reversing second subarray
reverse(arr, P, N - 1);
// Printing output
Console.Write(arr[K - 1]);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach.
/* Function to get pivot. For array 4, 3, 2, 1, 6, 5
it returns 3 (index of 1) */
function findPivot(arr, low, high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
let mid = parseInt((low + high) / 2, 10); /*low + (high - low)/2;*/
if (mid < high && arr[mid] < arr[mid + 1])
return mid;
if (mid > low && arr[mid] > arr[mid - 1])
return (mid - 1);
if (arr[low] <= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
function reverse(i, j, arr)
{
let y = j - 1;
for(let x = i; x < j; x++)
{
arr[x] = arr[y];
y--;
}
}
// Given Input
let arr = [ 10, 8, 6, 5, 2, 1, 13, 12 ];
let N = arr.length;
let K = 3;
// Function Call
let P = findPivot(arr, 0, N - 1);
// reversing first subarray
reverse(0, P + 1, arr);
// reversing second subarray
reverse(P + 1, N, arr);
// printing output
document.write(arr[K - 1]);
// This code is contributed by divyeshrabadiya07.
</script>
Producción
5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea óptima se basa en la observación de que el elemento R-th es el elemento más pequeño porque los elementos en el rango [1, R] están invertidos. Ahora, si el índice aleatorio es R , significa que el subarreglo [1, R] y [R + 1, N] están ordenados en orden decreciente . Por lo tanto, la tarea se reduce a encontrar el valor de R que se puede obtener mediante la búsqueda binaria . Finalmente, imprima el K -ésimo elemento más pequeño.
Siga los pasos a continuación para resolver el problema:
- Inicialice l como 1 yh como N para almacenar el índice de elementos de contorno del espacio de búsqueda para la búsqueda binaria .
- Bucle mientras el valor de l+1 < h
- Almacene el elemento central en una variable, mid como (l+h)/2 .
- Si arr[l] ≥ arr[mid]. Si es cierto, verifique en el lado derecho de mid actualizando l a mid .
- De lo contrario, actualice r a mid .
- Ahora, después de encontrar R , si K ≤ R , entonces la respuesta es arr[R-K+1]. De lo contrario, arr[N-(KR)+1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the Kth element in a
// sorted and rotated array at random point
int findkthElement(vector<int> arr, int n, int K)
{
// Set the boundaries for binary search
int l = 0;
int h = n - 1, r;
// Apply binary search to find R
while (l + 1 < h)
{
// Initialize the middle element
int mid = (l + h) / 2;
// Check in the right side of mid
if (arr[l] >= arr[mid])
l = mid;
// Else check in the left side
else
h = mid;
}
// Random point either l or h
if (arr[l] < arr[h])
r = l;
else
r = h;
// Return the kth smallest element
if (K <= r + 1)
return arr[r + 1 - K];
else
return arr[n - (K - (r + 1))];
}
// Driver Code
int main()
{
// Given Input
vector<int> arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
int n = arr.size();
int K = 3;
// Function Call
cout << findkthElement(arr, n, K);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
class GFG{
// Function to find the Kth element in a
// sorted and rotated array at random point
public static int findkthElement(int arr[], int n, int K)
{
// Set the boundaries for binary search
int l = 0;
int h = n - 1, r;
// Apply binary search to find R
while (l + 1 < h)
{
// Initialize the middle element
int mid = (l + h) / 2;
// Check in the right side of mid
if (arr[l] >= arr[mid])
l = mid;
// Else check in the left side
else
h = mid;
}
// Random point either l or h
if (arr[l] < arr[h])
r = l;
else
r = h;
// Return the kth smallest element
if (K <= r + 1)
return arr[r + 1 - K];
else
return arr[n - (K - (r + 1))];
}
// Driver Code
public static void main(String args[])
{
// Given Input
int []arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
int n = arr.length;
int K = 3;
// Function Call
System.out.println(findkthElement(arr, n, K));
}
}
// This code is contributed by SoumikMondal
Python3
# Python program for the above approach # Function to find the Kth element in a # sorted and rotated array at random point def findkthElement(arr, n, K): # Set the boundaries for binary search l = 0 h = n-1 # Apply binary search to find R while l+1 < h: # Initialize the middle element mid = (l+h)//2 # Check in the right side of mid if arr[l] >= arr[mid]: l = mid # Else check in the left side else: h = mid # Random point either l or h if arr[l] < arr[h]: r = l else: r = h # Return the kth smallest element if K <= r+1: return arr[r+1-K] else: return arr[n-(K-(r+1))] # Driver Code if __name__ == "__main__": # Given Input arr = [10, 8, 6, 5, 2, 1, 13, 12] n = len(arr) K = 3 # Function Call print(findkthElement(arr, n, K) )
C#
using System.IO;
using System;
class GFG {
// Function to find the Kth element in a
// sorted and rotated array at random point
public static int findkthElement(int[] arr, int n,
int K)
{
// Set the boundaries for binary search
int l = 0;
int h = n - 1, r;
// Apply binary search to find R
while (l + 1 < h) {
// Initialize the middle element
int mid = (l + h) / 2;
// Check in the right side of mid
if (arr[l] >= arr[mid])
l = mid;
// Else check in the left side
else
h = mid;
}
// Random point either l or h
if (arr[l] < arr[h])
r = l;
else
r = h;
// Return the kth smallest element
if (K <= r + 1)
return arr[r + 1 - K];
else
return arr[n - (K - (r + 1))];
}
static void Main()
{
// Given Input
int[] arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
int n = arr.Length;
int K = 3;
// Function Call
Console.WriteLine(findkthElement(arr, n, K));
}
}
// This code is contributed by abhinavjain194.
Javascript
<script>
// Function to find the Kth element in a
// sorted and rotated array at random point
function findkthElement(arr, n, K) {
// Set the boundaries for binary search
var l = 0;
var h = n - 1,
r;
// Apply binary search to find R
while (l + 1 < h) {
// Initialize the middle element
var mid = parseInt((l + h) / 2);
// Check in the right side of mid
if (arr[l] >= arr[mid]) l = mid;
// Else check in the left side
else h = mid;
}
// Random point either l or h
if (arr[l] < arr[h]) r = l;
else r = h;
// Return the kth smallest element
if (K <= r + 1) return arr[r + 1 - K];
else return arr[n - (K - (r + 1))];
}
// Given Input
var arr = [10, 8, 6, 5, 2, 1, 13, 12];
var n = arr.length;
var K = 3;
// Function Call
document.write(findkthElement(arr, n, K));
</script>
Producción
5
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA