I have a list of integers which needs to be sorted on the basis of number of digit 5 they contain. I have to implement comparator interface for it.
Note(case): If two numbers have same number of '5' or they don't contain '5' then they should be in ascending order.
Example: 525,155,555,15,5555
Output: 15,155,525,555,5555
Explanation:
15 has one '5' digit
155 has two '5' digits
525 has two '5' digits
555 has three digits
5555 has four '5' digits.
based on this they should be sorted.
Note: 525 and 155 both have same number of '5' digits so they are in ascending order.
My code is partially working, It is not sorting numbers with same numbers of '5' digit.
import java.util.*;
public class ClassComparable {
public static void main(String[] args) {
Integer arr[] = {155,85555,15, 405, 555, 510, 20, 150, 50, 85, 5505, 555, 959};
List<Integer> list = Arrays.asList(arr);
System.out.println("before =" list);
list.sort(new ClassComparable().new NumberOfFivesComparator());
System.out.println("after=" list);
}
class NumberOfFivesComparator implements Comparator<Integer> {
@Override
public int compare(Integer t2, Integer t1) {
int countInT1 = 0;
int countInT2 = 0;
while (t2 != 0) {
if (t2 % 10 == 5) {
countInT2 ;
}
t2 = t2 / 10;
}
while (t1 != 0) {
if (t1 % 10 == 5) {
countInT1 ;
}
t1= t1 / 10;
}
if(countInT1<countInT2) return 1;
if (countInT1>countInT2) return -1;
//if same number of '5's or no '5's are there then they must have ascending order, //help!!!!!!!!!!!!
if(t1<t2) return 1;
if (t1>t2) return -1;
return 0;
}
}
}
OUTPUT
before =[155, 85555, 15, 405, 555, 510, 20, 150, 50, 85, 5505,555,959]
after=[20, 15, 405, 510, 150, 50, 85, 959, 155, 555, 5505, 555,85555]
> Error=[15, 405, 510, 150, 50, 85, 959] have one '5' digits but they are not in ascending order. same error with [555, 5505, 555].
expected out put= [20,15,50,85,150,405,510,959,155,555,555,5505,85555]
CodePudding user response：
You're counting the 5s incorrectly.
If your treat the number as a String and count the 5s in like this:
class Scratch {
public static void main(String[] args) {
Integer arr[] = {155,85555,15, 405, 555, 510, 20, 150, 50, 85, 5505, 555, 959};
List<Integer> list = Arrays.asList(arr);
System.out.println("before =" list);
list.sort(Scratch::compare);
System.out.println("after=" list);
}
public static int compare(Integer t2, Integer t1) {
long countInT1 = t1.toString().chars().filter(c -> c=='5').count();
long countInT2 = t2.toString().chars().filter(c -> c=='5').count();
if(countInT1<countInT2) return 1;
if(countInT1>countInT2) return -1;
if(t1<t2) return 1;
if(t1>t2) return -1;
return 0;
}
}
it prints
before =[155, 85555, 15, 405, 555, 510, 20, 150, 50, 85, 5505, 555, 959]
after=[20, 15, 50, 85, 150, 405, 510, 959, 155, 555, 555, 5505, 85555]
CodePudding user response：
When comparing the integer values t1 and t2 in NumberOfFivesComparator.compare, both values are 0 due to the algorithm done before.
while (t2 != 0) {
if (t2 % 10 == 5) {
countInT2 ;
}
t2 = t2 / 10;
}
This loop will only exit when t2=0, so after both loops have completed, both t1 and t2 will be 0, thus it will not affect the following sort. In other words, the method returns 0 for any two numbers, that have the same number of 5s.
To fix this, either use a different method to calculate the number of 5s, as f1sh suggested, or use temporary variables for the algorithm.
for (int t2temp = t2; t2temp != 0;) {
if (t2temp % 10 == 5) {
countInT2 ;
}
t2temp = t2temp / 10;
}
CodePudding user response：
I made it just count the characters, it works fine so far:
public static void main(String[] args) {
Integer arr[] = {155,85555,15, 405, 555, 510, 20, 150, 50, 85, 5505, 555, 959};
List<Integer> list = Arrays.asList(arr);
System.out.println("before =" list);
list.sort((o1, o2) -> {
long c1 = getCounted5sOfInteger(o1);
long c2 = getCounted5sOfInteger(o2);
if (c1 != c2) {
return Long.compare(c1, c2);
} else {
return Long.compare(o1, o2);
}
});
System.out.println("after=" list);
}
private static long getCounted5sOfInteger(int i) {
return String.valueOf(i).chars().filter(c -> c == '5').count();
}
Output:
before =[155, 85555, 15, 405, 555, 510, 20, 150, 50, 85, 5505, 555, 959]
after=[20, 15, 50, 85, 150, 405, 510, 959, 155, 555, 555, 5505, 85555]
CodePudding user response：
Here is how I would approach it.
First, create a lambda to count the fives. This also caters to negative numbers in the list.
Function<Integer, Integer> countFives = s -> {
int count = 0;
while (s != 0) {
int k = s % 10;
if (Math.abs(k) == 5) {
count ;
}
s /= 10;
}
return count;
};
You could use the above function in a comparator directly. But I would create a map where the keys are the numbers and the values are the counts. This way, the counting of the fives is only done once for each value vs multiple times in a comparator. For small lists though it doesn't really matter. The lookup overhead of a map is minimal.
Map<Integer, Integer> counts =
list.stream().collect(Collectors.toMap(n -> n,
countFives, (dup, n) -> n));
Now define the comparator. First compare on the count and if equal, then on the actual numbers.
Comparator<Integer> comp = (a, b) -> {
int v = Integer.compare(counts.get(a), counts.get(b));
return v == 0 ? Integer.compare(a, b) : v;
};
Here is an example
List<Integer> list = new ArrayList<>(
List.of(-525, 155, 555, 15, 5, 15, -15, -5555));
list.sort(comp);
System.out.println(list);
prints
[-15, 5, 15, 15, -525, 155, 555, -5555]
Here is how the comparator might look without the map being used.
Comparator<Integer> comp = (a, b) -> {
int ac = countFives.apply(a);
int bc = countFives.apply(b);
int v = Integer.compare(ac,bc);
return v == 0 ? Integer.compare(a, b) : v;
};