Dado un arr[] que consta de N elementos en el rango [1, N] , la tarea es maximizar la distancia entre el elemento de array más pequeño y el más grande mediante un solo intercambio.
Ejemplos:
Entrada: arr[] = {1, 4, 3, 2}
Salida: 3
Explicación:
El intercambio de arr[1] y arr[3] maximiza la distancia.
Entrada: arr[] = {1, 6, 5, 3, 4, 7, 2}
Salida: 6
Explicación:
El intercambio de arr[5] y arr[6] maximiza la distancia.
Acercarse
- Encuentre los índices de 1 y N en la array.
- Sean minIdx y maxIdx el mínimo y el máximo de los dos índices, respectivamente.
- Ahora, maxIdx – minIdx es la distancia actual entre los dos elementos. Se puede maximizar por el máximo posible de los siguientes dos intercambios:
- Intercambiando a[minIdx] con a[0] aumentando la distancia en minIdx .
- Intercambiando a[maxIdx] con a[N – 1] aumentando la distancia en N – 1 – maxIdx .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program maximize the // distance between smallest // and largest array element // by a single swap #include <bits/stdc++.h> using namespace std; // Function to maximize the distance // between the smallest and largest // array element by a single swap int find_max_dist(int arr[], int N) { int minIdx = -1, maxIdx = -1; for (int i = 0; i < N; i++) { if (arr[i] == 1 || arr[i] == N) { if (minIdx == -1) minIdx = i; else { maxIdx = i; break; } } } return maxIdx - minIdx + max(minIdx, N - 1 - maxIdx); } // Driver Code int main() { int arr[] = { 1, 4, 3, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout << find_max_dist(arr, N) << endl; return 0; }
Java
// Java program maximize the distance // between smallest and largest array // element by a single swap import java.util.*; class GFG{ // Function to maximize the distance // between the smallest and largest // array element by a single swap static int find_max_dist(int arr[], int N) { int minIdx = -1, maxIdx = -1; for(int i = 0; i < N; i++) { if (arr[i] == 1 || arr[i] == N) { if (minIdx == -1) minIdx = i; else { maxIdx = i; break; } } } return maxIdx - minIdx + Math.max(minIdx, N - 1 - maxIdx); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 4, 3, 2 }; int N = arr.length; System.out.print(find_max_dist(arr, N) + "\n"); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program maximize the # distance between smallest # and largest array element # by a single swap # Function to maximize the distance # between the smallest and largest # array element by a single swap def find_max_dist(arr, N): minIdx, maxIdx = -1, -1 for i in range(N): if (arr[i] == 1 or arr[i] == N): if (minIdx == -1) : minIdx = i else : maxIdx = i break return (maxIdx - minIdx + max(minIdx, N - 1 - maxIdx)) # Driver code arr = [ 1, 4, 3, 2 ] N = len(arr) print(find_max_dist(arr, N)) # This code is contributed by divyeshrabadiya07
C#
// C# program maximize the distance // between smallest and largest array // element by a single swap using System; class GFG{ // Function to maximize the distance // between the smallest and largest // array element by a single swap static int find_max_dist(int []arr, int N) { int minIdx = -1, maxIdx = -1; for(int i = 0; i < N; i++) { if (arr[i] == 1 || arr[i] == N) { if (minIdx == -1) minIdx = i; else { maxIdx = i; break; } } } return maxIdx - minIdx + Math.Max(minIdx, N - 1 - maxIdx); } // Driver Code public static void Main(String[] args) { int []arr = { 1, 4, 3, 2 }; int N = arr.Length; Console.Write(find_max_dist(arr, N) + "\n"); } } // This code is contributed by Amit Katiyar
Javascript
<script> // javascript program maximize the distance // between smallest and largest array // element by a single swap // Function to maximize the distance // between the smallest and largest // array element by a single swap function find_max_dist(arr , N) { var minIdx = -1, maxIdx = -1; for(i = 0; i < N; i++) { if (arr[i] == 1 || arr[i] == N) { if (minIdx == -1) minIdx = i; else { maxIdx = i; break; } } } return maxIdx - minIdx + Math.max(minIdx, N - 1 - maxIdx); } // Driver Code var arr = [ 1, 4, 3, 2 ]; var N = arr.length; document.write(find_max_dist(arr, N) + "\n"); // This code is contributed by Amit Katiyar </script>
Producción:
3
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA