arrays - 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. 创建一个以Integer作为键的字典。值类型无关紧要。
2. 遍历输入数组。对于输入数组中的每个值，检查该值是否在字典中。
3. 如果是，这是重复的，丢弃。
4. 如果不是，这是第一次遇到该值。保留该值，并将其添加到字典中。

字典的重点是它可以执行 O(1) 查找。

在伪代码中：

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);

显然，您需要创建和销毁字典。我假设你知道怎么做。而且我选择就地修改数组，但如果您愿意，您同样可以创建一个新数组。

Answer 2

这是一个没有字典的版本。

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;