I have encountered this question in my recent interview.
An array is given, I need to sort the array and all the duplicate elements should be at the end.
Example: input: {7,4,2,3,3,5,3,11,9,2}
Since 2 & 3 are repeated elements they should occur at the end of Array.
Output: {4,5,7,9,11,2,2,3,3,3}
I am free to use any other data structure. No constraints.
CREATE_ARRAY repeated, unique
SORT inputArray
ADD MINIMAL_POSSIBLE_VALUE TO inputArray
TRAVERSE inputArray i=index (from 2nd element to last):
IF inputArray[i-1] == inputArray[i]:
2X: ADD inputArray[i] TO repeated
i++
WHILE i < LENGTH(inputArray) - 1 and inputArray[i-1] == inputArray[i]:
ADD inputArray[i] TO repeated
i++
ELSE:
ADD inputArray[i-1] TO unique
PRINT MERGED(unique, repeated)
You will be sorting your array so duplicate values form patches. You will then distribute the array to unique values array and repeated values array and print them both.
The third line ADD MINIMAL_POSSIBLE_VALUE TO inputArray just adds a dummy element to the array that will never get printed but saves you some IF statements.
// algorithm
function algorithm(input) {
input.sort(function(a, b) { return a - b });
input.push(Number.MIN_VAL);
var repeated = [], unique = [];
for (var i = 1; i < input.length; i++) {
if (input[i - 1] == input[i]) {
repeated.push(input[i], input[i]);
i++;
while (i < input.length - 1 && input[i - 1] == input[i]) {
repeated.push(input[i]);
i++;
}
} else {
unique.push(input[i - 1]);
}
}
return unique.concat(repeated);
}
// driver
inputBox = document.getElementById('input-box');
outputBox = document.getElementById("output-box");
inputBox.addEventListener("keyup", function() {
outputBox.innerHTML = algorithm(inputBox.value.split(/[\s,]+/).map(Number));
});<input id="input-box">
<div id="output-box"></div>
Solution with C# using the sort method of List
static void Main(string[] args)
{
List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2, 5 };
List<int> tmp = new List<int> { };
List<int> rep = new List<int> {};
//sorting the list
list.Sort();
for (var i = 0; i < list.Count(); i++)
{
int cantidad = list.LastIndexOf(list[i]) - list.IndexOf(list[i]);
if ( cantidad != 0)
{
//found repetitions
rep.AddRange(list.GetRange(list.IndexOf(list[i]), cantidad + 1));
i += cantidad;
}
else tmp.Add(list[i]);
}
tmp.AddRange(rep);
foreach (int data in tmp)
Console.WriteLine(data);
Console.ReadLine();
}
Solution with C# sorting out manually
static void Main(string[] args)
{
List<int> list = new List<int> { 7, 4, 2, 3, 3, 5, 3, 11, 9, 2 };
List<int> tmp = new List<int> {};
List<int> rep = new List<int> {};
foreach (int data in list)
{
if (tmp.Count() > 0)
{
int posicion = -1;
bool bandera = false;
for (var i=0; i < tmp.Count(); i++)
{
//searching a repetition
if (tmp[i] == data)
{
tmp.RemoveAt(i);
//adding to the repeated list at the end or in a determined position
for (var j = 0; j < rep.Count(); i++)
{
if (rep[j] > data)
{
bandera = true;
rep.Insert(j, data); //the one that was deleted
rep.Insert(j, data); //the one at the original list
break;
}
}
if (!bandera)
{
bandera = true;
rep.Add(data); //the one that was deleted
rep.Add(data); //the one at the original list
}
break;
}
//saving the position to be inserted
if (tmp[i] > data)
{
posicion = i;
break;
}
}
//was not a repetition
if (!bandera)
{
bool banderaRep = false;
//searching in the repeated list
for (var i = 0; i < rep.Count(); i++)
{
if (rep[i] == data)
{
banderaRep = true;
rep.Insert(i, data);
break;
}
}
//was not in the repeated list
if (!banderaRep)
{
if (posicion == -1)
tmp.Add(data);
else
tmp.Insert(posicion, data);
}
}
}
else
tmp.Add(data);
}
//join
tmp.AddRange(rep);
foreach (int data in tmp)
Console.WriteLine(data);
Console.ReadLine();
}
Solution using a map data structure, not a very efficient solution but it works nonetheless:
1> Traverse through the vector counting frequency of numbers in a map
2> Iterate over the map (elements will be in sorted order) pushing unique elements in a vector and repeated elements in another vector
3> Push repeated elements in the sorted array
Code in C++
vector<int> sortUnique(const vector<int> & nums) {
// Step 1
map<int, int> numFreq;
for (auto it : nums) {
if (numFreq.count(it) == 0) {
numFreq[it] = 1;
}
else {
numFreq[it]++;
}
}
// Step 2
vector<int> sorted;
sorted.reserve(nums.size());
vector<int> repeated;
repeated.reserve(nums.size());
for (auto it : numFreq) {
if (it.second == 1) {
sorted.push_back(it.first);
}
else {
for (int i = 0; i < it.second; i++) {
repeated.push_back(it.first);
}
}
}
// Push repeated elements at the end
for (auto it : repeated) {
sorted.push_back(it);
}
return sorted;
}
I will use Swift 3 (beta 3) to describe an high level implementation for your problem.
let list = [7,4,2,3,3,5,3,11,9,2]
let countedSet = NSCountedSet(array: list)
let singles = list.filter { countedSet.count(for: $0) == 1 }
let duplicates = list.filter { countedSet.count(for: $0) > 1 }
let res = singles.sorted() + duplicates.sorted()
This class creates an index, it associate to each value it number of occurrencies.
Here I am filtering the original array. I am putting into singles the values with only 1 occurrences and into duplicates the values that appear more then once.
Finally I sort singles and duplicates and I concatenate them
{7,4,5,11,9,3,3,2,2}? That is, does the order of the items matter, so long as the single are to the left and the repeated are to the right?