给定一个包含n个不同元素的数组，将给定数组转换为所有元素都在0到n-1范围内的形式。元素的顺序是相同的，即0被放置在最小元素的位置，1被放置在第二小元素的位置，n-1被放置在最大元素的位置。
null
Input: arr[] = {10, 40, 20}Output: arr[] = {0, 2, 1}Input: arr[] = {5, 10, 40, 30, 20}Output: arr[] = {0, 1, 4, 3, 2}
预期的时间复杂度为O（n logn）。
我们强烈建议您在继续解决方案之前单击此处并进行练习。
方法1（简单） 一个简单的解决方案是首先找到最小元素，用0替换它，考虑剩余数组并在剩余数组中找到最小值并用1替换它，等等。该解的时间复杂度为O（n） 2. )
方法2（高效） 其想法是使用哈希和排序。以下是步骤。 1) 创建一个临时数组，并将给定数组的内容复制到temp[]。这需要O（n）时间。 2) 按升序排序temp[]。这需要O（n logn）时间。 3) 创建一个空哈希表。这需要O（1）个时间。 4) 从左到右遍历temp[]，并将数字及其值的映射（在转换的数组中）存储在哈希表中。这平均需要O（n）个时间。 5) 遍历给定的数组，并使用哈希表将元素更改为它们的位置。这平均需要O（n）个时间。
该解决方案的总体时间复杂度为O（n logn）。
下面是上述想法的实现。
C++
// C++ program to convert an array in reduced // form #include <bits/stdc++.h> using namespace std; void convert( int arr[], int n) { // Create a temp array and copy contents // of arr[] to temp int temp[n]; memcpy (temp, arr, n* sizeof ( int )); // Sort temp array sort(temp, temp + n); // Create a hash table. Refer unordered_map< int , int > umap; // One by one insert elements of sorted // temp[] and assign them values from 0 // to n-1 int val = 0; for ( int i = 0; i < n; i++) umap[temp[i]] = val++; // Convert array by taking positions from // umap for ( int i = 0; i < n; i++) arr[i] = umap[arr[i]]; } void printArr( int arr[], int n) { for ( int i=0; i<n; i++) cout << arr[i] << " " ; } // Driver program to test above method int main() { int arr[] = {10, 20, 15, 12, 11, 50}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Given Array is " ; printArr(arr, n); convert(arr , n); cout << "Converted Array is " ; printArr(arr, n); return 0; } |
JAVA
// Java Program to convert an Array // to reduced form import java.util.*; class GFG { public static void convert( int arr[], int n) { // Create a temp array and copy contents // of arr[] to temp int temp[] = arr.clone(); // Sort temp array Arrays.sort(temp); // Create a hash table. HashMap<Integer, Integer> umap = new HashMap<>(); // One by one insert elements of sorted // temp[] and assign them values from 0 // to n-1 int val = 0 ; for ( int i = 0 ; i < n; i++) umap.put(temp[i], val++); // Convert array by taking positions from // umap for ( int i = 0 ; i < n; i++) arr[i] = umap.get(arr[i]); } public static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver code public static void main(String[] args) { int arr[] = { 10 , 20 , 15 , 12 , 11 , 50 }; int n = arr.length; System.out.println( "Given Array is " ); printArr(arr, n); convert(arr , n); System.out.println( "Converted Array is " ); printArr(arr, n); } } // This code is contributed by Abhishek Panwar |
Python3
# Python3 program to convert an array # in reduced form def convert(arr, n): # Create a temp array and copy contents # of arr[] to temp temp = [arr[i] for i in range (n) ] # Sort temp array temp.sort() # create a map umap = {} # One by one insert elements of sorted # temp[] and assign them values from 0 # to n-1 val = 0 for i in range (n): umap[temp[i]] = val val + = 1 # Convert array by taking positions from umap for i in range (n): arr[i] = umap[arr[i]] def printArr(arr, n): for i in range (n): print (arr[i], end = " " ) # Driver Code if __name__ = = "__main__" : arr = [ 10 , 20 , 15 , 12 , 11 , 50 ] n = len (arr) print ( "Given Array is " ) printArr(arr, n) convert(arr , n) print ( "Converted Array is " ) printArr(arr, n) # This code is contributed by Abhishek Gupta |
C#
// C# Program to convert an Array // to reduced form using System; using System.Collections.Generic; using System.Linq; class GFG { public static void convert( int []arr, int n) { // Create a temp array and copy contents // of []arr to temp int []temp = new int [arr.Length]; Array.Copy(arr, 0, temp, 0, arr.Length); // Sort temp array Array.Sort(temp); // Create a hash table. Dictionary< int , int > umap = new Dictionary< int , int >(); // One by one insert elements of sorted // []temp and assign them values from 0 // to n - 1 int val = 0; for ( int i = 0; i < n; i++) if (umap.ContainsKey(temp[i])) umap[temp[i]] = val++; else umap.Add(temp[i], val++); // Convert array by taking positions from // umap for ( int i = 0; i < n; i++) arr[i] = umap[arr[i]]; } public static void printArr( int []arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver code public static void Main(String[] args) { int []arr = {10, 20, 15, 12, 11, 50}; int n = arr.Length; Console.WriteLine( "Given Array is " ); printArr(arr, n); convert(arr , n); Console.WriteLine( "Converted Array is " ); printArr(arr, n); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript Program to convert an Array // to reduced form function convert(arr, n) { // Create a temp array and copy contents // of arr[] to temp let temp = [...arr]; // Sort temp array temp.sort((a, b) => a - b); // Create a hash table. let umap = new Map(); // One by one insert elements of sorted // temp[] and assign them values from 0 // to n-1 let val = 0; for (let i = 0; i < n; i++) umap.set(temp[i], val++); // Convert array by taking positions from // umap for (let i = 0; i < n; i++) arr[i] = umap.get(arr[i]); } function prletArr(arr, n) { for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } // Driver program let arr = [10, 20, 15, 12, 11, 50]; let n = arr.length; document.write( "Given Array is " + "<br/>" ); prletArr(arr, n); convert(arr , n); document.write( "<br/>" + "Converted Array is " + "<br/>" ); prletArr(arr, n); </script> |
输出：
Given Array is 10 20 15 12 11 50 Converted Array is 0 4 3 2 1 5
本文由 德埃拉吉·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
