Remove duplicate array elements

Question

I need to remove all duplicate values from an array of integer, yet maintain the order of the elements:

Example:

10,20,20(duplicate),10(duplicate),50

Becomes:

10,20,50

Answer 1

1. Create a dictionary with Integer as the key. The value type is immaterial.
2. Iterate through the input array. For each value in the input array, check whether or not that value is in the dictionary.
3. If yes, this is a duplicate, discard.
4. If no, this is the first time the value has been encountered. Retain the value, and add it to the dictionary.

The point of the dictionary is that it can perform O(1) lookup.

In pseudocode:

var
  arr: TArray<Integer>; // input and output
  Dict: TDictionary<Integer, Integer>;
  SrcIndex, DestIndex: Integer;
....
DestIndex := 0;
for SrcIndex := 0 to high(arr) do begin
  Value := arr[SrcIndex];
  if not Dict.ContainsKey(Value) then begin
    arr[DestIndex] := arr[SrcIndex];
    Dict.Add(Value, 0);
    inc(DestIndex);
  end;
end;
SetLength(arr, DestIndex);

Obviously you need to create, and destroy, the dictionary. I'm assuming you know how to do that. And I've opted to modify the array in place but you could equally create a new array if you prefer.

Answer 2

heres a version without dictionary.

procedure TForm1.RemoveDuplicates;
var
  i,j,k,tot,mov:integer;
  arr:array of integer;
begin
  arr := [10,20,30,40,30,20,10,10,50,10,20,40];
  tot := 0;
  for i := 0 to length(arr)-1 do
  begin
    if i >= length(arr)-tot-1 then
      break;
    for j := i + 1 to length(arr)-1-tot do
    begin
      if j >= length(arr)-tot-1 then
        break;
      mov := 0;
      while arr[i] = arr[j] do
      begin
        inc(mov);
        arr[j] := arr[j+mov];
      end;
      tot := tot + mov;
      if mov>0 then
        for k := j+1 to length(arr)-1-tot do
          arr[k] := arr[k+mov];
    end;
  end;
  SetLength(arr,length(arr)-tot-1);
end;