java sort array where it's position matters

Question

lets say i have this array

int [] array= new int[26];

it has 26 places because the position 0 is 'a' , position 1'b' ... position 25 is 'z' so in each position i have an int number so

if in position array[0]=5 it means i have 5 'a'
if in position array[1]=6 it means i have 6'b'
if in position array[0]=0 it means that i do not have the 'a' letter

what i want is to find in each loop the 2 smallest frequencies and the letters of the two smallest frequencies

for(int i=0;i<array.length;i++)
        if(array[i]==0)
        continue;       
        else{
            cmin1=(char)('a'+i);
            posi=i;                 
            min1=array[posi] ;
            break;
        }
            for(int j=posi+1;j<array.length;j++){
            if(array[j]==0)
                continue;   
            else if(array[j]<=min1){
                posj=posi;
                posi=j;
                cmin2=cmin1;
                cmin1=(char)(j+'a');    
                min2=min1;
                min1=array[j];
            }

i have tried this which is wrong

i have tried to find the smallest letter but i cannot find the second smallest especially if the frequencies increase in each time — user2180352
– user2180352, Commented Mar 19, 2013 at 16:39
Since this is homework, I'll just outline a solution. Loop through the array. If the element is smaller than the smallest you've found, clear a List and add the position in a List. If the element is the same as the smallest you've found, add the position in a List. When the loop is finished, you'll have a List of the smallest occurrences. Take the first two. — Gilbert Le Blanc
– Gilbert Le Blanc, Commented Mar 19, 2013 at 16:47

user2147970 · Accepted Answer · 2013-03-19 16:44:10Z

2

Java is Object Oriented so...

Let's take a class, which name would be LetterFrequency LetterFrequency has 2 attributes: 1) Char character 2) Integer occurrences

You need to sort the LetterFrequency objects by their "occurrences" atrribute. To do that, make LetterFrequancy implements Comparable and define method compareTo() accordingly.

Then put all your LetterFrequency objects in a List and use the method

Lists.sort(yourList)

answered Mar 19, 2013 at 16:44

user2147970

4122 silver badges7 bronze badges

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

Comments

scharette · Accepted Answer · 2013-03-19 16:55:55Z

0

Sort would work but it's not the best performing method.

How about a single loop which would be O(n)?

int min1 = Integer.MAX_INT;
int idx1 = -1;
int min2 = Integer.MAX_INT;
int idx2 = -1;

for(int i=0;i<array.length;i++) {
    // skip empty items
    if(array[i]==0)
         continue;

    if (array[i] < min1) {
         min2 = min1;
         idx2 = idx1;
         min1 = array[i];
         idx1 = i;
    }
    else if (array[i] < min2) {
         min2 = array[i];
         idx2 = i;
    }
}

answered Mar 19, 2013 at 16:55

scharette

6351 gold badge9 silver badges26 bronze badges

Comments

karan · Accepted Answer · 2013-03-19 16:43:29Z

0

sort the array first...now apply the searching algorithm...and here you go once you find the smallest element you can get the second smallest as the array is already sorted...i guess there would be no difficulty doing this...for sorting you can use quicksort with complexity(nlogn)...hope it helps you

answered Mar 19, 2013 at 16:43

karan

8,8734 gold badges45 silver badges81 bronze badges

Comments

dsh · Accepted Answer · 2013-03-19 16:47:09Z

I would create a class representing each frequency count. Then I would create a Comparator which orders the records by the frequency. Then I would use Arrays.sort() or Collections.sort() to sort the collection using the Comparator.

Alternatively, if you simply want to find the entries in the array but can't change your data type, then you need to define an algorithm for searching (not sorting) the array. To do this, and do it in one pass, I would define local variables for the positions and corresponding frequencies of the two least frequently occurring. Initialize the least to the first item in the array, then proceed by comparing the current one and if it is less then rotate the values of the variables which are keeping track. At the end you'll have the two least frequent.

Pith · Accepted Answer · 2013-03-19 16:50:01Z

0

If you just want to find the smallest element in an array, you can use the following code :

List<int> list = Arrays.asList(ArrayUtils.toObject(array));

// Print the smallest element of your array
System.out.println(Collections.min(list));

edited Mar 19, 2013 at 16:50

answered Mar 19, 2013 at 16:44

Pith

3,8043 gold badges34 silver badges45 bronze badges

Comments

Costis Aivalis · Accepted Answer · 2013-03-19 16:53:21Z

0

First of all, this array declaration will never work:

 int [] array= new array[26];

You need:

 int [] array= new int[26];

answered Mar 19, 2013 at 16:53

Costis Aivalis

13.8k3 gold badges49 silver badges48 bronze badges

Collectives™ on Stack Overflow

java sort array where it's position matters

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related