CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
Mahesh Reddy
Mahesh Reddy

Reputation: 31

Find the number of times a number is repeated in an array in less than O(n^2)

Sample code that I have written.But this is n^2

int a[]={1,4,1,5,2,2,4,3,4,1};
int b[][]=new int[5][2];
int i,j,k=0,count=1;
boolean temp=false;
for(i=0;i<a.length;i++)
{
    for(j=0;j<5;j++)
    {
        if(a[i]==b[j][0])
        {   temp=true;
            b[j][1]++;
            break;
        }
    }

    if(temp==false)
    {
        b[k][0]=a[i];
        b[k][1]=1;
        k++;    
    }
    temp=false;
}
for(i=0;i<5;i++)
{
    for(j=0;j<1;j++)
    {
    System.out.println(b[i][j]+" is repeated "+b[i][j+1]+" times");
    }
}

Upvotes: 3

Views: 9862

Answers (9)

elliot42
elliot42

Reputation: 3764

Option 1: sacrifice memory for speed.

  • Use a data structure like a HashMap to record frequencies of each number.
  • Iterate through in O(n) time to build the frequency counts, then either iterate through whole HashMap or extract one value.

Option 2: sort

  • Sort, then either iterate through the whole sorted structure or O(log n) to seek to a particular value.
    • Quicksort has average n log n, O(n^2) worst case, is in-place for memory.
    • Mergesort or heapsort are O(n log n) but takes up extra memory during sort

Upvotes: 5

BiGYaN
BiGYaN

Reputation: 7159

Reducing O(n^2) to O(n*log n) is simple in this case:

  1. Sort the numbers using heapsort/quicksort ... O(n*log n)
  2. Traverse the array once and count unique elements and get their counts ... O(n)

Keeping a height balanced tree with numbers as keys along with the occurrence count is another idea which will give O(n*log n). I don't see an O(n) solution without using a hash-table like data structure which is readily available in most languages.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533620

If you can alter the existing array you can do this. Its O(n log(n)) and doesn't create an new objects. (If you cannot alter the original you can clone it.) Its much more efficient than maintaining a Map. ;)

int a[] = {1, 4, 1, 5, 2, 2, 4, 3, 4, 1};

Arrays.sort(a);
int last = a[0];
int count = -1; 
for (int i : a) {
    if (i == last) {
        count++;
        continue;
    }
    System.out.println("Number " + last + " found " + count + " times.");
    count = 1;
    last = i;
}
System.out.println("Number " + last + " found " + count + " times.");

prints

Number 1 found 3 times.
Number 2 found 2 times.
Number 3 found 1 times.
Number 4 found 3 times.
Number 5 found 1 times.

Upvotes: 0

user unknown
user unknown

Reputation: 36239

Why do you use a 2-dim array? If your numbers are known to be in range 1..5, use the index for the number:

    int a[] = {1,4,1,5,2,2,4,3,4,1};
    int b[] = new int[5];

    for (int n : a)
        ++b[n-1];

    for (int j=0; j < 5; ++j)
        System.out.println (j + " is repeated " + b [j-1] + " times");
  • Don't declare Variables premature, and don't reuse them. You will forget to delete unused variables (count), and get hard to analyze code.
  • Use the improved for : loop.
  • Declare counters in the head - there is a reason why this is allowed: for (int i = ...) and why i isn't visible outside the block. It's not expensive. No, it isn't. Look at the bytecode.

Upvotes: 0

Swagatika
Swagatika

Reputation: 3436

You can achive in O(n) time by creating another datastructure like map. Ex: int a[]={1,4,1,5,2,2,4,3,4,1};

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for(int i = 0; i < a.length ; i++)
{
    if(map.containsKey(a[i]))
    {
        map.put(a[i], map.get(a[i])+1);
    }
    else
    {
        map.put(a[i], 1);
    }
}

System.out.print(map);

Result: {1=3, 2=2, 3=1, 4=3, 5=1}

Upvotes: 1

dting
dting

Reputation: 39287

Pseudocode:

counts = dictionary default to 0

for each element in list:
    counts[element]+=1

O(n)

Upvotes: 3

Ingo
Ingo

Reputation: 36339

A fast sorting algorithm should be much faster than O(n^2), and that followed by a group, which is O(n) should still be faster than O(n^2).

Therefore, in pseudocode:

    group (sort [1,2,3,3,2,1])   =>   [(1,2), (2,2), (3,2)]

Upvotes: 1

tamasgal
tamasgal

Reputation: 26309

You should use eg. merge sort to sort your array and then use a simple for-loop to go through the whole array to count the repeats.

Merge sort has n*log(n) and a for-loop to find the repeats is also quick.

Upvotes: 2

ThiefMaster
ThiefMaster

Reputation: 318548

Here's a solution in pseudocode:

Map<Int, Int> histogram;
for(number in array) {
    histogram[number]++;
}

Now histogram[somenumber] contains the number of times the number is in the array - in O(n) assuming the Map looks up items in O(1)

Upvotes: 7

Related Questions