List of integers in C
Given an array of size n and a number k, find all elements that appear more than n/k timesGiven an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3. Show Recommended: Please try your approach on {IDE} first, before moving on to the solution.A simple method is to pick all elements one by one. For every picked element, count its occurrences by traversing the array, if count becomes more than n/k, then print the element. Time Complexity of this method would be O(n2). We can solve the above problem in O(nk) time using O(k-1) extra space. Note that there can never be more than k-1 elements in output (Why?). There are mainly three steps in this algorithm. 1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements. struct eleCount { int element; int count; }; struct eleCount temp[];This step takes O(k) time. 3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time. The main step is step 2, how to maintain (k-1) potential candidates at every point? The steps used in step 2 are like famous game: Tetris. We treat each number as a piece in Tetris, which falls down in our temporary array temp[]. Our task is to try to keep the same number stacked on the same column (count in temporary array is incremented). Consider k = 4, n = 9 Given array: 3 1 2 2 2 1 4 3 3 i = 0 3 _ _ temp[] has one element, 3 with count 1 i = 1 3 1 _ temp[] has two elements, 3 and 1 with counts 1 and 1 respectively i = 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 1 respectively. i = 3 - - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 2 respectively. i = 4 - - 2 - - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 3 respectively. i = 5 - - 2 - 1 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 2 and 3 respectively.Now the question arises, what to do when temp[] is full and we see a new element we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element. i = 6 - - 2 - 1 2 temp[] has two elements, 1 and 2 with counts as 1 and 2 respectively. i = 7 - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 1, 1 and 2 respectively. i = 8 3 - 2 3 1 2 temp[] has three elements, 3, 1 and 2 with counts as 2, 1 and 2 respectively.Finally, we have at most k-1 numbers in temp[]. The elements in temp are {3, 1, 2}. Note that the counts in temp[] are useless now, the counts were needed only in step 2. Now we need to check whether the actual counts of elements in temp[] are more than n/k (9/4) or not. The elements 3 and 2 have counts more than 9/4. So we print 3 and 2. Note that the algorithm doesnt miss any output element. There can be two possibilities, many occurrences are together or spread across the array. If occurrences are together, then count will be high and wont become 0. If occurrences are spread, then the element would come again in temp[]. Following is the implementation of the above algorithm. C++
Java
Python3
C#
Output
First Test
Number:4 Count:3
Second Test
Number:2 Count:2
Third Test
Number:2 Count:2
Fourth Test
Number:2 Count:2
Number:3 Count:2
Time Complexity: O(nk) Another Approach: Hashing can also be an efficient solution. With a good hash function, we can solve the above problem in O(n) time on average. Extra space required hashing would be higher than O(k). Also, hashing cannot be used to solve the above variations with O(1) extra space. Below is the implementation of the above idea: C++
Java
Python3
C#
Javascript
Output
1
2
Method #2:Using Built-in Python functions:
Below is the implementation: C++
Java
Python3
C#
Javascript
Output: 1 2Time Complexity: O(N) ?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p
Article Tags :
Arrays Searching
Practice Tags :
Arrays Searching
Read Full Article
|