I have a List<List<Integer>> that has an arbitrary number of variable length List<Integer>. I need to compare each value at the same index and make sure those values are sorted meaning the first list should be smaller than the next based on index by index values.
In the below example, each index would be compared between the lists at index i = 0, the values are all int 5 so continue. For i = 1, the values are all 3, so continue. For i = 2, listA is larger because it has an additional integer where as the others are null and should return false.
List<List<Integer>> listOfLists = List.of(List.of(5, 3, 2), // A
List.of(5, 3), // B
List.of(5, 3)); // C
Another example. Here, these are not in the correct order because listB fails on the last index because ListA and listC have values as they are not null, so listB is smaller.
List<List<Integer>> listOfLists = List.of(List.of(4, 3, 2, 1), // A
List.of(4, 3, 2), // B
List.of(4, 3, 2, 1)); // C
In this example, they are in order.
List<List<Integer>> listOfLists = List.of(List.of(4, 3), // A
List.of(4, 3, 1), // B
List.of(5, 3, 2, 1), // C
List.of(5, 4, 3)); // D
I have tried many options. I have tried to use Comparator to create a custom compare method, nested for loops, recursion, etc. I keep running into problems with IndexOutOfBOundsExceptions and this is still kind of mind boggling for me. I have been able to sort the lists or find the maximum values of the lists and compare them to the others, but not while maintaining the order.
I feel like pushing each value at the same index onto a stack and then comparing them would be a good solution, but I am having trouble implementing it.
The end result is I need to determine if List<List<Integer>> is in proper order from smallest to largest and return true; otherwise, return false. The last example would be true and the others would be false.
EDIT
I came up with this and it seems to work.
public class ListTest {
public static void main(String... args) {
List<List<Integer>> listOfLists = List.of(List.of(3, 2, 1), // A
List.of(4, 3, 1), // B
List.of(5, 4, 3)); // C
boolean correctOrder = true;
int max = getMaxLength(listOfLists);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < max; i ) {
for (int j = 0; j < listOfLists.size(); j ) {
try {
stack.push(listOfLists.get(j).get(i));
} catch(IndexOutOfBoundsException ex) {
stack.push(0);
}
}
if (!isSorted(stack)) {
correctOrder = false;
break;
}
}
System.out.println(correctOrder);
}
public static boolean isSorted(Stack<Integer> stack) {
int temp = stack.pop();
while (!stack.isEmpty()) {
int compare = stack.pop();
if (temp < compare)
return false;
temp = compare;
}
return true;
}
public static int getMaxLength(List<List<Integer>> list) {
int maxLength = 0;
for (int i = 0; i < list.size(); i ) {
if (list.get(i).size() > maxLength) {
maxLength = list.get(i).size();
System.out.println(maxLength);
}
}
return maxLength;
}
}
CodePudding user response：
So you need a comparator. This is pretty easy. Just create two separate comparators: first should sort lists by size, secodn - by content.
public static Comparator<List<Integer>> createComparator() {
Comparator<List<Integer>> sortBySizeAsc = Comparator.comparingInt(List::size);
Comparator<List<Integer>> sortByContentAsc = (one, two) -> {
Iterator<Integer> it1 = one.iterator();
Iterator<Integer> it2 = two.iterator();
while (it1.hasNext() && it2.hasNext()) {
int res = Integer.compare(it1.next(), it2.next());
if (res != 0)
return res;
}
return 0;
};
return sortBySizeAsc.thenComparing(sortByContentAsc);
}
CodePudding user response：
You could sort a copy of your lists acording to your order definition and check if the copy and original are equal. (Might be not the efficient way to do if your list are very big).
static boolean areListsInOrder(List<List<Integer>> listOfLists){
//a comparator to sort your lists comparing each value index wise, then comparing by list size
Comparator<List<Integer>> comp = (list1,list2) -> IntStream.range(0, Math.min(list1.size(), list2.size()))
.map(i -> list1.get(i).compareTo(list2.get(i)))
.dropWhile( i -> i == 0).findFirst()
.orElse(Integer.compare(list1.size(), list2.size()));
//copy your list and sort
List<List<Integer>> copy = new ArrayList<>(listOfLists);
copy.sort(comp);
//check if the sorted and original are equal
return copy.equals(listOfLists);
}
CodePudding user response：
As far as I have understood what you're trying to achieve, below should be the solution:
boolean checkListsOrder(List<List<Integer>> listOfLists) {
int maxSize = 0;
for (List<Integer> singleList : listOfLists)
maxSize = maxSize > singleList.size() ? maxSize : singleList.size();
Map<Integer, Integer> checkIfAllValuesEqualsAndWrongOrdered = new HashMap<>();
for (int i = 0; i < listOfLists.size(); i )
checkIfAllValuesEqualsAndWrongOrdered.put(i, 0);
for (int j = 0; j < maxSize; j ) {
TreeMap<Integer, Integer> orderOfValues = new TreeMap<>();
for (int i = 0; i < listOfLists.size(); i ) {
if (j < listOfLists.get(i).size()) {
orderOfValues.put(i, listOfLists.get(i).get(j));
}
}
Map.Entry<Integer, Integer> previousEntry = orderOfValues.firstEntry();
Map.Entry<Integer, Integer> nextEntry = orderOfValues.higherEntry(previousEntry.getKey());
while (nextEntry != null) {
if (previousEntry.getValue() > nextEntry.getValue())
return false;
else if (previousEntry.getValue() == nextEntry.getValue() && listOfLists.get(previousEntry.getKey()).size() > listOfLists.get(nextEntry.getKey()).size()) {
if (checkIfAllValuesEqualsAndWrongOrdered.get(nextEntry.getKey()) 1 == listOfLists.get(nextEntry.getKey()).size() - 1)
return false;
else
checkIfAllValuesEqualsAndWrongOrdered.put(nextEntry.getKey(), checkIfAllValuesEqualsAndWrongOrdered.get(nextEntry.getKey()) 1);
}
previousEntry = nextEntry;
nextEntry = orderOfValues.higherEntry(nextEntry.getKey());
}
}
return true;
}