Created
August 11, 2022 18:52
-
-
Save rquackenbush/87e4fefd22459d1184aa03eed024c92e to your computer and use it in GitHub Desktop.
One (non-optimized) solution for a Stack Overflow question.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
/* | |
Example 1 | |
input : nums = [2,4,2,2,7,5,6,7,8,6,6,2,6,7,6] | |
output : nums = [2,4,5,6,8,6] | |
Example 2 input : nums = [2,2,3,2,3,2] | |
output : nums = [2,3,3] | |
*/ | |
public class Program | |
{ | |
private static int[] RemoveLastTriplet(int[] input) | |
{ | |
var toRemove = new bool[input.Length]; | |
var counts = new Dictionary<int, int>(); | |
foreach(var value in input) | |
{ | |
int count; | |
if (counts.TryGetValue(value, out count)) | |
{ | |
counts[value] = count + 1; | |
} | |
else | |
{ | |
counts[value] = 1; | |
} | |
} | |
foreach(var kvp in counts) | |
{ | |
//Determine how many triplets we have for this value | |
var tripletCount = kvp.Value / 3; | |
//Keep track of where we're starting | |
var currentIndex = input.Length - 1; | |
//Remove each triplet | |
for(var tripletIndex = 0; tripletIndex < tripletCount; tripletIndex++) | |
{ | |
//counts the number of elements in this triplet | |
var thisTripletCount = 0; | |
//Mark each member of the triplet for deletion. | |
for(var inputIndex = currentIndex; thisTripletCount < 3; inputIndex--) | |
{ | |
if (input[inputIndex] == kvp.Key) | |
{ | |
//Mark this index for removal | |
toRemove[inputIndex] = true; | |
thisTripletCount++; | |
} | |
//Keep track of where we are in the overall input array | |
currentIndex--; | |
} | |
} | |
} | |
//We could be more clever here and keep track of how many | |
// items we'll have in the output list and just create an array. | |
var output = new List<int>(); | |
for(int index = 0; index < input.Length; index++) | |
{ | |
if (!toRemove[index]) | |
{ | |
output.Add(input[index]); | |
} | |
} | |
return output.ToArray(); | |
} | |
public static void Main() | |
{ | |
//var input = new int[] { 2,4,2,2,7,5,6,7,8,6,6,2,6,7,6 }; | |
var input = new int[] { 2,2,3,2,3,2 }; | |
var output = RemoveLastTriplet(input); | |
output.Dump(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment