How to count different values ​​in a list in linear time?

Question

I might think about sorting them and then iterating over each element one by one, but this is nlogn. Is there a linear method for counting individual items in a list?

Answer 1

Update: - other than unique

---

If you are looking for "unique" values (as if you see the "JASON" element more than once, than it is no longer unique and should not be considered)

You can do this in linear time using a HashMap ;)

(Generalized / linguistic agnostic idea hash table )

Each HashMap / Hash table entry is a <KEY, VALUE> pair, where the keys are unique (but there are no restrictions on their corresponding value in the pair)

Step 1:

Iterate over all the items in the list once: O (n)

• For each element seen in the list, check if it is already in HashMap O (1), it is depreciated
  • If not, add it to the HashMap with the item value in the list as KEY and the number of times you saw this value, since VALUE O (1)
  • If so, increase the number of times you saw this KEY so far O (1)

Step 2:

Iterate through HashMap and count KEYS with VALUE exactly 1 (thus unique) O (n)

Analysis:

• Lead time: O (n), amortized
• Space: O (U), where U is the number of different values.

---

If you are looking for “excellent” values ​​(as if you want to count the number of different elements), use a HashSet instead of a HashMap / Hash table, and then simply request the size of the HashSet.

Answer 2

You can adapt this extremely cool O (n) -time and O (1) -space algorithm in place to remove duplicates to the task of counting different values ​​- just count the number of values ​​equal to the sentinel value in the final O (n) pass, and subtract it from the size of the list.

Answer 3

Add each list item to the HashSet , and then check the size (power) of the HashSet, which is the number of different values ​​in the list.