How to determine which number occurs most often in an array?-CodePudding

How do I determine which value occurs the most after I filled the array with 100 random values which are between 1 and 11? It is a simple question, but I can't seem to find any straight answers online.

CodePudding user response：

Here is a sample code:

procedure TForm1.Button1Click(Sender: TObject);

  function Calculate: Integer;
  var
    Numbers: array [1..100] of Byte;
    Counts: array [1..11] of Byte;
    I: Byte;
  begin
    // Fill the array with random numbers
    for I := Low(Numbers) to High(Numbers) do
      Numbers[I] := Random(11)   1;
    // Count the occurencies
    ZeroMemory(@Counts, SizeOf(Counts));
    for I := Low(Numbers) to High(Numbers) do
      Inc(Counts[Numbers[I]]);
    // Identify the maximum
    Result := Low(Counts);
    for I := Low(Counts)   1 to High(Counts) do
      if Counts[I] > Counts[Result] then
        Result := I;
  end;

begin
  ShowMessage(Calculate.ToString);
end;

CodePudding user response：

It is a simple question [...]

Yes

but I can't seem to find any straight answers online.

You shouldn't be searching for solutions on-line; instead, you should start to think about how to design an algorithm able to solve the problem. For this, you may need pen and paper.

First, we need some data to work with:

const
  ListLength = 100;
  MinValue = 1;
  MaxValue = 11;

function MakeRandomList: TArray<Integer>;
begin
  SetLength(Result, ListLength);
  for var i := 0 to High(Result) do
    Result[i] := MinValue   Random(MaxValue - MinValue   1);
end;

The MakeRandomList function creates a dynamic array of integers. The array contains ListLength = 100 integers ranging from MinValue = 1 to MaxValue = 11, as desired.

Now, given such a list of integers,

var L := MakeRandomList;

how do we find the most frequent value?

Well, if we were to solve this problem without a computer, using only pen and paper, we would probably count the number of times each distinct value (1, 2, ..., 11) occurs in the list, no?

Then we would only need to find the value with the greatest frequency.

For instance, given the data

2, 5, 1, 10, 1, 5, 2, 7, 8, 5

we would count to find the frequencies

Then we read the table from the top line to the bottom line to find the row with the greatest frequency, constantly keeping track of the current winner.

Now that we know how to solve the problem, it is trivial to write a piece of code that performs this algorithm:

procedure FindMostFrequentValue(const AList: TArray<Integer>);
type
  TValueAndFreq = record
    Value: Integer;
    Freq: Integer;
  end;
var
  Frequencies: TArray<TValueAndFreq>;
begin

  if Length(AList) = 0 then
    raise Exception.Create('List is empty.');

  SetLength(Frequencies, MaxValue - MinValue   1);

  // Step 0: Label the frequency list items

  for var i := 0 to High(Frequencies) do
    Frequencies[i].Value := i   MinValue;

  // Step 1: Obtain the frequencies

  for var i := 0 to High(AList) do
  begin
    if not InRange(AList[i], MinValue, MaxValue) then
      raise Exception.CreateFmt('Value out of range: %d', [AList[i]]);
    Inc(Frequencies[AList[i] - MinValue].Freq);
  end;

  // Step 2: Find the winner

  var Winner: TValueAndFreq;
  Winner.Value := 0;
  Winner.Freq := 0;

  for var i := 0 to High(Frequencies) do
    if Frequencies[i].Freq > Winner.Freq then
      Winner := Frequencies[i];

  ShowMessageFmt('The most frequent value is %d with a count of %d.',
    [Winner.Value, Winner.Freq]);

end;

CodePudding user response：

Delphi has a TDictionary class, which you can use to implement a frequency map, eg:

uses 
  ..., System.Generics.Collections;

function Calculate: Integer;
var
  Frequencies: TDictionary<Integer, Integer>;
  I, Key, Value, MaxFreq: Integer;
  Elem: TPair<Integer, Integer>;
begin
  Frequencies := TDictionary<Integer, Integer>.Create;
  // Fill the dictionary with random numbers
  for I := 1 to 100 do begin
    Key := Random(11)   1;
    if not Frequencies.TryGetValue(Key, Value) then Value := 0;
    Frequencies.AddOrSetValue(Key, Value   1);
  end;  
  // Identify the maximum
  Result := 0; 
  MaxFreq := 0;
  for elem in Frequencies do begin
    if elem.Value > MaxFreq then begin
      MaxFreq := elem.Value;
      Result := elem.Key;
    end;
  end;
  Frequencies.Free;
end;