Convert an array to reduced form | Set 1 (Simple and Hashing) - GeeksforGeeks
Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element.
http://www.geeksforgeeks.org/convert-array-reduced-form-set-2-using-vector-pairs/
The idea is to create a vector of pairs. Every element of pair contains element and index. We sort vector by array values. After sorting, we copy indexes to original array.
Read full article from Convert an array to reduced form | Set 1 (Simple and Hashing) - GeeksforGeeks
Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element.
A Simple Solution is to first find minimum element replace it with 0, consider remaining array and find minimum in the remaining array and replace it with 1 and so on. Time complexity of this solution is O(n2)
The idea is to use hashing and sorting. Below are steps.
1) Create a temp array and copy contents of given array to temp[]. This takes O(n) time.
2) Sort temp[] in ascending order. This takes O(n Log n) time.
3) Create an empty hash table. This takes O(1) time.
4) Traverse temp[] form left to right and store mapping of numbers and their values (in converted array) in hash table. This takes O(n) time on average.
5) Traverse given array and change elements to their positions using hash table. This takes O(n) time on average.
1) Create a temp array and copy contents of given array to temp[]. This takes O(n) time.
2) Sort temp[] in ascending order. This takes O(n Log n) time.
3) Create an empty hash table. This takes O(1) time.
4) Traverse temp[] form left to right and store mapping of numbers and their values (in converted array) in hash table. This takes O(n) time on average.
5) Traverse given array and change elements to their positions using hash table. This takes O(n) time on average.
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]];
}
http://www.geeksforgeeks.org/convert-array-reduced-form-set-2-using-vector-pairs/
The idea is to create a vector of pairs. Every element of pair contains element and index. We sort vector by array values. After sorting, we copy indexes to original array.
void
convert(
int
arr[],
int
n)
{
// A vector of pairs. Every element of
// pair contains array element and its
// index
vector <pair<
int
,
int
> > v;
// Put all elements and their index in
// the vector
for
(
int
i = 0; i < n; i++)
v.push_back(make_pair(arr[i], i));
// Sort the vector by array values
sort(v.begin(), v.end());
// Put indexes of modified vector in arr[]
for
(
int
i=0; i<n; i++)
arr[i] = v[i].second;
}