Se le da una array ordenada rotada y su objetivo es restaurar su clasificación original en su lugar.
Se espera que use O(1) espacio extra y O(n) complejidad de tiempo.
Ejemplos:
Input : [3, 4, 1, 2] Output : [1, 2, 3, 4] Input : [2, 3, 4, 1] Output : [1, 2, 3, 4]
Encontramos el punto de rotación. Luego rotamos la array usando el algoritmo de inversión .
1. First, find the split point where the sorting breaks.
2. Then call the reverse function in three steps.
- From zero index to split index.
- From split index to end index.
- From zero index to end index.
C++
// C++ implementation for restoring original
// sort in rotated sorted array
#include <bits/stdc++.h>
using namespace std;
// Function to restore the Original Sort
void restoreSortedArray(int arr[], int n)
{
for (int i = 0; i < n; i++) {
if (arr[i] > arr[i + 1]) {
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
reverse(arr, arr+i+1);
reverse(arr + i + 1, arr + n);
reverse(arr, arr + n);
}
}
}
// Function to print the Array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
// Driver function
int main()
{
int arr[] = { 3, 4, 5, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
restoreSortedArray(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java implementation for restoring original
// sort in rotated sorted array
class GFG
{
// Function to restore the Original Sort
static void restoreSortedArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
if (arr[i] > arr[i + 1])
{
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
reverse(arr,0,i);
reverse(arr , i + 1, n);
reverse(arr,0, n);
}
}
}
static void reverse(int[] arr, int i, int j)
{
int temp;
while(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Function to print the Array
static void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 5, 1, 2 };
int n = arr.length;
restoreSortedArray(arr, n - 1);
printArray(arr, n);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 implementation for restoring original # sort in rotated sorted array # Function to restore the Original Sort def restoreSortedArray(arr, n): for i in range(n): if (arr[i] > arr[i + 1]): # In reverse(), the first parameter # is iterator to beginning element # and second parameter is iterator # to last element plus one. reverse(arr, 0, i); reverse(arr, i + 1, n); reverse(arr, 0, n); def reverse(arr, i, j): while (i < j): temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i += 1; j -= 1; # Function to print the Array def printArray(arr, size): for i in range(size): print(arr[i], end=""); # Driver code if __name__ == '__main__': arr = [3, 4, 5, 1, 2]; n = len(arr); restoreSortedArray(arr, n - 1); printArray(arr, n); # This code is contributed by 29AjayKumar
C#
// C# implementation for restoring original
// sort in rotated sorted array
using System;
class GFG
{
// Function to restore the Original Sort
static void restoreSortedArray(int []arr, int n)
{
for (int i = 0; i < n; i++)
{
if (arr[i] > arr[i + 1])
{
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
reverse(arr,0,i);
reverse(arr , i + 1, n);
reverse(arr,0, n);
}
}
}
static void reverse(int[] arr, int i, int j)
{
int temp;
while(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Function to print the Array
static void printArray(int []arr, int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 3, 4, 5, 1, 2 };
int n = arr.Length;
restoreSortedArray(arr, n - 1);
printArray(arr, n);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation for restoring original
// sort in rotated sorted array
// Function to restore the Original Sort
function restoreSortedArray(arr, n)
{
for (let i = 0; i < n; i++)
{
if (arr[i] > arr[i + 1])
{
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
reverse(arr,0,i);
reverse(arr , i + 1, n);
reverse(arr,0, n);
}
}
}
function reverse(arr, i, j)
{
let temp;
while(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
// Function to print the Array
function printArray(arr, size)
{
for (let i = 0; i < size; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr = [ 3, 4, 5, 1, 2 ];
let n = arr.length;
restoreSortedArray(arr, n - 1);
printArray(arr, n)
</script>
Producción:
1 2 3 4 5
Podemos realizar una búsqueda binaria para encontrar el punto de rotación como se explica aquí .
Enfoque de código eficiente usando búsqueda binaria:
- Primero encuentre el índice del elemento mínimo (índice dividido) en la array usando la búsqueda binaria
- Luego llame a la función inversa en tres pasos.
- De índice cero a índice dividido.
- Del índice dividido al índice final.
- Del índice cero al índice final.
C++
// C++ implementation for restoring original
// sort in rotated sorted array using binary search
#include <bits/stdc++.h>
using namespace std;
// Function to find start index of array
int findStartIndexOfArray(int arr[], int low,int high)
{
if (low>high)
{
return -1;
}
if (low == high)
{
return low;
}
int mid = low + (high-low)/2;
if(arr[mid] > arr[mid+1])
return mid+1;
if(arr[mid-1] > arr[mid])
return mid;
if(arr[low] > arr[mid])
return findStartIndexOfArray(arr, low, mid-1);
else
return findStartIndexOfArray(arr, mid+1, high);
}
// Function to restore the Original Sort
void restoreSortedArray(int arr[], int n)
{
// array is already sorted
if (arr[0] < arr[n-1])
return;
int start = findStartIndexOfArray(arr, 0, n-1);
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
reverse(arr, arr + start);
reverse(arr + start, arr + n);
reverse(arr, arr + n);
}
// Function to print the Array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
// Driver function
int main()
{
int arr[] = { 1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
restoreSortedArray(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java implementation for restoring original
// sort in rotated sorted array using binary search
import java.util.*;
class GFG
{
// Function to find start index of array
static int findStartIndexOfArray(int arr[],
int low, int high)
{
if (low > high)
{
return -1;
}
if (low == high)
{
return low;
}
int mid = low + (high - low) / 2;
if (arr[mid] > arr[mid + 1])
{
return mid + 1;
}
if (arr[mid - 1] > arr[mid])
{
return mid;
}
if (arr[low] > arr[mid])
{
return findStartIndexOfArray(arr, low, mid - 1);
}
else
{
return findStartIndexOfArray(arr, mid + 1, high);
}
}
// Function to restore the Original Sort
static void restoreSortedArray(int arr[], int n)
{
// array is already sorted
if (arr[0] < arr[n - 1])
{
return;
}
int start = findStartIndexOfArray(arr, 0, n - 1);
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
Arrays.sort(arr, 0, start);
Arrays.sort(arr, start, n);
Arrays.sort(arr);
}
// Function to print the Array
static void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
restoreSortedArray(arr, n);
printArray(arr, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation for restoring original # sort in rotated sorted array using binary search # Function to find start index of array def findStartIndexOfArray(arr, low, high): if (low > high): return -1; if (low == high): return low; mid = low + (high - low) / 2; if (arr[mid] > arr[mid + 1]): return mid + 1; if (arr[mid - 1] > arr[mid]): return mid; if (arr[low] > arr[mid]): return findStartIndexOfArray(arr, low, mid - 1); else: return findStartIndexOfArray(arr, mid + 1, high); # Function to restore the Original Sort def restoreSortedArray(arr, n): # array is already sorted if (arr[0] < arr[n - 1]): return; start = findStartIndexOfArray(arr, 0, n - 1); # In reverse(), the first parameter # is iterator to beginning element # and second parameter is iterator # to last element plus one. reverse(arr, 0, start); reverse(arr, start, n); reverse(arr); # Function to print the Array def printArray(arr, size): for i in range(size): print(arr[i], end=""); def reverse(arr, i, j): while (i < j): temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i += 1; j -= 1; # Driver code if __name__ == '__main__': arr = [ 1, 2, 3, 4, 5 ]; n = len(arr); restoreSortedArray(arr, n); printArray(arr, n); # This code is contributed by PrinciRaj1992
C#
// C# implementation for restoring original
// sort in rotated sorted array using binary search
using System;
class GFG
{
// Function to find start index of array
static int findStartIndexOfArray(int []arr,
int low, int high)
{
if (low > high)
{
return -1;
}
if (low == high)
{
return low;
}
int mid = low + (high - low) / 2;
if (arr[mid] > arr[mid + 1])
{
return mid + 1;
}
if (arr[mid - 1] > arr[mid])
{
return mid;
}
if (arr[low] > arr[mid])
{
return findStartIndexOfArray(arr, low, mid - 1);
}
else
{
return findStartIndexOfArray(arr, mid + 1, high);
}
}
// Function to restore the Original Sort
static void restoreSortedArray(int []arr, int n)
{
// array is already sorted
if (arr[0] < arr[n - 1])
{
return;
}
int start = findStartIndexOfArray(arr, 0, n - 1);
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
Array.Sort(arr, 0, start);
Array.Sort(arr, start, n);
Array.Sort(arr);
}
// Function to print the Array
static void printArray(int []arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 3, 4, 5};
int n = arr.Length;
restoreSortedArray(arr, n);
printArray(arr, n);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation for restoring original
// sort in rotated sorted array using binary search
// Function to find start index of array
function findStartIndexOfArray(arr, low, high)
{
if (low > high)
{
return -1;
}
if (low == high)
{
return low;
}
let mid = low + parseInt((high - low) / 2, 10);
if (arr[mid] > arr[mid + 1])
{
return mid + 1;
}
if (arr[mid - 1] > arr[mid])
{
return mid;
}
if (arr[low] > arr[mid])
{
return findStartIndexOfArray(arr, low,
mid - 1);
}
else
{
return findStartIndexOfArray(arr, mid + 1,
high);
}
}
// Function to restore the Original Sort
function restoreSortedArray(arr, n)
{
// Array is already sorted
if (arr[0] < arr[n - 1])
{
return;
}
let start = findStartIndexOfArray(arr, 0, n - 1);
// In reverse(), the first parameter
// is iterator to beginning element
// and second parameter is iterator
// to last element plus one.
arr.sort();
}
// Function to print the Array
function printArray(arr, size)
{
for(let i = 0; i < size; i++)
{
document.write(arr[i] + " ");
}
}
// Driver code
let arr = [ 1, 2, 3, 4, 5 ];
let n = arr.length;
restoreSortedArray(arr, n);
printArray(arr, n);
// This code is contributed by decode2207
</script>
Producción:
1 2 3 4 5
Este artículo es una contribución de Kshitiz Gupta . 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 review-team@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