CODEWITHSUNDEEP
calgorithm
DonaldT
DonaldT

Reputation: 103

algorithm which finds the numbers in a sequence which appear 3 times or more, and prints their indexes

Suppose I input a sequence of numbers which ends with -1. I want to print all the values of the sequence that occur in it 3 times or more, and also print their indexes in the sequence.

For example , if the input is : 2 3 4 2 2 5 2 4 3 4 2 -1 so the expected output in that case is : 

2: 0 3 4 6 10
4: 2 7 9

First I thought of using quick-sort , but then I realized that as a result I will lose the original indexes of the sequence. I also have been thinking of using count, but that sequence has no given range of numbers - so maybe count will be no good in that case.

Now I wonder if I might use an array of pointers (but how?) Do you have any suggestions or tips for an algorithm with time complexity O(nlogn) for that ? It would be very appreciated.

Upvotes: 1

Views: 315

Answers (3)

Jonathan Olson
Jonathan Olson

Reputation: 1186

Starting with a sorted list is a good idea.

You could create a second array of original indices and duplicate all of the memory moves for the sort on the indices array. Then checking for triplicates is trivial and only requires sort + 1 traversal.

Upvotes: 0

domenico popolizio
domenico popolizio

Reputation: 26

First of all, sorry for my bad english (It's not my language) I'll try my best. So similar to what @vvigilante told, here is an algorithm implemented in python (it is in python because is more similar to pseudo code, so you can translate it to any language you want, and moreover I add a lot of comment... hope you get it!)

from typing import Dict, List

def three_or_more( input_arr:int ) -> None:
  indexes: Dict[int, List[int]] = {}

  #scan the array
  i:int
  for i in range(0, len(input_arr)-1):
    #create list for the number in position i
    # (if it doesn't exist)
    #and append the number
    indexes.setdefault(input_arr[i],[]).append(i)

  #for each key in the dictionary
  n:int
  for n in indexes.keys():

    #if the number of element for that key is >= 3
    if len(indexes[n]) >= 3:

      #print the key
      print("%d: "%(n), end='')

      #print each element int the current key
      el:int
      for el in indexes[n]:
        print("%d,"%(el), end='')

      #new line
      print("\n", end='')    

#call the function
three_or_more([2, 3, 4, 2, 2, 5, 2, 4, 3, 4, 2, -1])

Complexity: The first loop scan the input array = O(N).

The second one check for any number (digit) in the array,

since they are <= N (you can not have more number than element), so it is O(numbers) the complexity is O(N).

The loop inside the loop go through all indexes corresponding to the current number...

the complexity seem to be O(N) int the worst case (but it is not)

So the complexity would be O(N) + O(N)*O(N) = O(N^2)

but remember that the two nest loop can at least print all N indexes, and since the indexes are not repeated the complexity of them is O(N)...

So O(N)+O(N) ~= O(N)

Speaking about memory it is O(N) for the input array + O(N) for the dictionary (because it contain all N indexes) ~= O(N).

Well if you do it in c++ remember that maps are way slower than array, so if N is small, you should use an array of array (or std::vector> ), else you can also try an unordered map that use hashes

P.S. Remember that get the size of a vector is O(1) time because it is a difference of pointers!

Upvotes: 0

vvigilante
vvigilante

Reputation: 133

Keep it simple! The easiest way would be to scan the sequence and count the number of occurrence of each element, put the elements that match the condition in an auxiliary array.

Then, for each element in the auxiliary array, scan the sequence again and print out the indices.

Upvotes: 1

Related Questions