Frequency algorithm of element inside array in time O(n)

Question

I wanted to ask if there is an algorithm that can find, in an array of length n, if there is an array element with a certain frequency percentage (10%, 20% etc...) in linear time.

Selection sort is O(n^2) and the majority algorithm even if O(n) can only find if the number is repeated at least n/2 times.

just iterate over the array, count occurences and divide by the number of elements? — UmNyobe
– UmNyobe, Commented Jul 22, 2014 at 7:46
In O(n)? If i count the occurrences of every element I have to iterate over the array n times so complexity will be n^2, i thought about something like counting sort but the interval of numbers is not known — Vignusky
– Vignusky, Commented Jul 22, 2014 at 7:58
if you apply count sort then only one time iteration will be done means complexity is O(n) and getting count of that number is in O(1) — Devavrata
– Devavrata, Commented Jul 22, 2014 at 8:02
Are there restrictions on space usage? You can simply create a dictionary mapping elements to count. This takes an additional O(n) space for an algorithm that runs in O(n) time. — tobias_k
– tobias_k, Commented Jul 22, 2014 at 8:15
Why do a radix sort at all? Just create a dictionary. If that's a bit more spacious than necessary, who cares? Create dict, iterate list, increase counters, iterate dict to find frequent numbers. — tobias_k
– tobias_k, Commented Jul 22, 2014 at 9:10

LeartS · Accepted Answer · 2014-07-22 11:27:15Z

1

You are making this out to be a lot harder than it really is, assuming you don't have space limits.

The idea is to iterate the array and save the count of each element while doing so. Dictionary (or equivalent structure) lookup is O(1) so it's not a problem.
Then just iterate over the dictionary and see what elements have the required frequency.

Python pseudocode:

for elem in array:
    count[elem] = count.get(elem, 0) + 1
for elem, elem_count in count.items():
    if 0.20 <= float(elem_count) / len(array) <= 0.25:
        print "{} has a frequency between 20% and 25%".format(elem)

edited Jul 22, 2014 at 11:27

answered Jul 22, 2014 at 11:20

LeartS

2,9162 gold badges27 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

InbalIta · Accepted Answer · 2014-07-22 08:18:23Z

0

int counter = 0; (no influence on run time in this code line).
Iterate the arry using loop (for,while,whatever). For each element:
- if(element == what_you_search)
counter++;

//This if statment is o(1) in each iteration, there were n interation so in the overall it is
//o(n) for the whole loop.
int percentage = counter / (array.len()); //It is being done in o(1).

o(1) + o(n) + o(1) = o(n)

answered Jul 22, 2014 at 8:18

InbalIta

618 bronze badges

4 Comments

Henry Over a year ago

Please be careful with notation: o(n) is not the same as O(n).

InbalIta Over a year ago

Ohh misunderstood question.... in that case there is a diffent algorithm. don't remmember it's name.

InbalIta Over a year ago

I will write here pseudo code: SortedArray = Array accepted from any O(n) sorted array algorithm. (I know there are few like this just choose one). CheckElement = sortedArray[0] Counter = 1 for(int i = 1; i< array.len ; i++){ if(SortedArray[i] == CheckElement) Counter++; else{ if counter indicates elements shows 10% or whatever return true; else CheckElement = SortedArray[i]; } }

InbalIta Over a year ago

General idea is sorting array and then check how many equal values are repetead until get an index having a new element value, then see if counter of elements is ok for your criteria

Collectives™ on Stack Overflow

Frequency algorithm of element inside array in time O(n)

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related