is there another way of solving this problem ?

Question

i have a list 1 column and 100 rows each with a number the number on each row may not be unique i need to output the unique list of numbers sorted according to their rank , which is less if the number of its repetitions is more. least ranked number i.e 1 is on the top

now here is how i am planning to solve this problem

first i want to define an array of the structure would be like this

struct abc[100]
{
int number
int occurrence = 1;
}

now i want to go through the list for each row and check if the number exist in the array of structure or not. if it does not i want to store the number in a abc[row].number however if the number exists in the array of structure i want to increment the occurrence of that particular record.

at the end i would get a array of structure filled with each unique number and number of time it occurs together as records.

Is this style of programming a good way ? defining structures and moving through them is looking a tedious job to me can you suggest me a better way ? I'm a beginner programmer please feel free to give me any sort of advice

Answer 1

You could probably achieve something similar using a Hashtable<Integer, Integer>, that would avoid the need for defining any kind of structure and make your code a bit tidier. The first input to the Hashtable is the number you're tracking, the second input is the number of occurences of it.

Answer 2

Depends on whether you need blindingly fast speed for updates. If so, you may want to consider keeping the elements sorted by number and using a binary search to locate that number. This will reduce the time complexity from O(n) to O(log n).

Then, once all the numbers are inserted, you could sort by occurance (or occurrence) to rank them properly, or simply create a new list sorted by occurrence if you want to keep inserting into the original. This is assuming write operations will be more frequent than read operations (usual for this sort of behavior).

But it may be, in your case, that speed doesn't matter for 100 elements. The difference is between a maximum of 100 iterations (for linear search) and 7 iterations (for binary search).

Alternatively (and this is probably the best idea), use one of the mapping data structures already provided by Java. You should read and memorize this link :-)

You could use a HashTable<Integer,Integer> and not worry about the 100-element limitation. Tou're code size will be smaller since Sun have already done the hard yards getting it working.

Answer 3

Your way would work, some alternatives would be:

1. Load the data into a database, and use SQL to return the ranked, grouped, list.
2. Use built in Java objects as A S says.
3. If you were using .net you could use Linq.

Answer 4

Here is an example that returns a Map of item frequencies. The method is generic and will therefore work for any type of item, not just Integer. I'm returning a SortedMap (TreeMap implementation) and hence the function runs with complexity O(n log n). However, I could have opted for a HashMap implementation, reducing the complexity to O(n) (as insert performance for HashMap is O(1)).

import java.util.*;

public class Main {
  public static void main(String[] args) {
    List<Integer> l = new LinkedList<Integer>();
    l.add(5);
 l.add(10);
 l.add(2);
 l.add(5);
 l.add(20);

 System.err.println(freq(l));
  }

  private static <T> SortedMap<T, Integer> freq(Collection<? extends T> c) {
 SortedMap<T, Integer> ret = new TreeMap<T, Integer>();

 for (T t : c) {
     Integer fq = ret.get(t);
     ret.put(t, fq == null ? 1 : fq + 1);
 }

 return ret;
  }    
}

Answer 5

It is possible to use ADO with Excel.

Dim cn As Object
Dim rs As Object

strFile = Workbooks(1).FullName
strCon = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" & strFile _
    & ";Extended Properties=""Excel 8.0;HDR=No;IMEX=1"";"

Set cn = CreateObject("ADODB.Connection")
Set rs = CreateObject("ADODB.Recordset")

cn.Open strCon

strSQL = "SELECT Count(F1)  AS CountF1, F1 FROM [Sheet1$] GROUP BY F1 ORDER BY Count(F1) DESC"

rs.Open strSQL, cn

Sheets("Sheet2").Cells(2, 1).CopyFromRecordset rs