data-structures - 1回のパスで配列の個別の要素を数える方法は?

Question

1回のパスで整数の配列の個別の要素をカウントするアルゴリズムを教えてください。

たとえば、for ループを使用して配列を走査しようとすることができます

最初の要素を別の配列に格納します。その後の要素は 2 番目の配列の要素と比較され、異なる場合はその配列に格納し、カウンターをインクリメントします。

誰かがこれよりも優れたアルゴリズムを教えてくれますか?

c および c++ の使用

Answer 1

要素が整数で、その値が ～ の間0であると仮定しますMAXVAL-1。

#include <stdio.h>
#include <string.h>

#define MAXVAL 50

unsigned int CountDistinctsElements(unsigned int* iArray, unsigned int iNbElem) {
  unsigned int ret = 0;

  //this array will contains the count of each value
  //for example, c[3] will contain the count of the value 3 in your original array
  unsigned int c[MAXVAL];
  memset(c, 0, MAXVAL*sizeof(unsigned int));

  for (unsigned int i=0; i<iNbElem; i++) {
    unsigned int elem = iArray[i];
    if (elem < MAXVAL && c[elem] == 0) {
      ret++;
    }
    c[elem]++;
  }
  return ret;
}

int main() {
  unsigned int myElements[10] = {0, 25, 42, 42, 1, 2, 42, 0, 24, 24};
  printf("Distincts elements : %d\n", CountDistinctsElements(myElements, 10));
  return 0;
}

出力 : ( Ideone リンク)

特徴的な要素 : 6

Answer 2

編集：要素を数えたいだけだとは知りませんでした。以下のコードを更新しました。

int countUnique()
{
    uniqueArray[numElements];
    myArray[numElements];
    int counter = 0;
    int uniqueElements = 0;

    for(int i = 0; i < numElements; i++)
    {
       element tempElem = myArray[i];
       if(!doesUniqueContain(tempElem, counter, uniqueArray)//If it doesn't contain it
       {
            uniqueArray[counter] = tempElem;
            uniqueElements++;
       }
    }
    return uniqueElements;
}

bool doesUniqueContain(element oneElement, int counter, array *uniqueArray)
{
    if(counter == 0)
    {
        return false; //No elements, so it doesn't contain this element.
    }
    for(int i = 0; i < counter; i++)
    {
        if(uniqueArray[i] == oneElement)
            return true;
    }
    return false;
}

これは、ロジックを確認できるようにするためだけです