We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I got it to run with quicksort. What helped me was to remember to operate on copies of the arrays, since the approach of comparing with sorted and swapping elements destroys the map and the original input array. You need to compare for both asc and desc. One is just inversion of the other. Here is my C# verion with custom quick sort.
// Complete the lilysHomework function below.
static int lilysHomework(int[] arr) {
var originalIndexValueMap = new Dictionary<int, int>();
for (var i = 0; i < arr.Length; i++)
{
originalIndexValueMap[arr[i]] = i;
}
var sortedAsc = new int[arr.Length];
Array.Copy(arr, 0, sortedAsc, 0, arr.Length);
quicksort(sortedAsc, 0, arr.Length - 1);
var sortedDesc = new int[arr.Length];
Array.Copy(sortedAsc, 0, sortedDesc, 0, sortedAsc.Length);
Array.Reverse(sortedAsc);
var ascCount = Count(arr, sortedAsc, originalIndexValueMap);
var descCount = Count(arr, sortedDesc, originalIndexValueMap);
return Math.Min(ascCount, descCount);
}
static int Count(int[] a, int[] sorted, Dictionary<int, int> map)
{
var arr = new int[a.Length];
Array.Copy(a, 0, arr, 0, arr.Length);
var mapCopy = new Dictionary<int, int>();
foreach (var kv in map)
{
mapCopy[kv.Key] = kv.Value;
}
var count = 0;
for (var i = 0; i < arr.Length; i++)
{
if (arr[i] != sorted[i])
{
count++;
var indexToSwap = mapCopy[sorted[i]];
mapCopy[arr[i]] = indexToSwap;
var tmp = arr[i];
arr[i] = arr[indexToSwap];
arr[indexToSwap] = tmp;
}
}
return count;
}
static void quicksort(int[] arr, int left, int right)
{
var p = arr[(right + left) / 2];
int i = left;
int j = right;
while (i <= j)
{
while (arr[i] < p) {
i++;
}
while (arr[j] > p) {
j--;
}
if (i <= j)
{
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
if (left < j)
{
quicksort(arr, left, j);
}
if (right > i)
{
quicksort(arr, i, right);
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
I got it to run with quicksort. What helped me was to remember to operate on copies of the arrays, since the approach of comparing with sorted and swapping elements destroys the map and the original input array. You need to compare for both asc and desc. One is just inversion of the other. Here is my C# verion with custom quick sort.