лексикографическое сравнение двух массивов в java

Я хотел бы реализовать метод, который принимает 2 массива и возвращает тот, который лексикографически меньше другого. Пробовал делать по определению лексикографического порядка, но не получается. Вот мой код:

public boolean lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int m = 1;
    int n = list1.size() -1;


    while(m <= n)
    {
        boolean firstFound = true;
        for(int i=0; i<m; i++)
        {
            if(!Objects.equals(list1.get(i), list2.get(i)))
            {
                firstFound = false;
                break;
            }
        }

        if(firstFound && list1.get(m) < list2.get(m)) return true;
        m++;
    }

    return false;
}

Приведенный выше код не дает правильного ответа.

Например, для входных данных 0 5 7 9 14 16 18 23 и 1 3 6 11 12 17 20 22 ответ должен быть истинным, но я получил ложный.


lexicographic
person Rozion    schedule 14.11.2014    source источник
comment
в чем не работает? Есть ли ошибка?   -  person StackExchange What The Heck    schedule 14.11.2014
comment
Это не дает правильного ответа. Например, для входных данных 0 5 7 9 14 16 18 23 и 1 3 6 11 12 17 20 22 ответ должен быть правдой, но я получил ложь.   -  person Rozion    schedule 14.11.2014

Ответы (4)


arrow_upward
2
arrow_downward

Начиная с Java 9, Arrays.compare предоставляет стандартный способ сделать это.

Сравнивает два массива Object в сопоставимых элементах лексикографически.

Также существуют версии Arrays.compare для массивов длинных, двойных и т. д.

person Florent Guillaume    schedule 28.09.2020

arrow_upward
1
arrow_downward

Когда два массива отсортированы, мы можем просто проверить любой i, если массив1[i] ‹ массив2[i], то массив1 лексикографически меньше, чем массив2.

person Rozion    schedule 21.11.2014

arrow_upward
1
arrow_downward

Определение лексикографического порядка намного проще, чем то, что вы реализовали.

public boolean lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int n = list1.size();

    for(int i = 0; i < n; i++)
    {
        if(list1.get(i) < list2.get(i)) 
        {
            return true;
        }
    }

    return false;
}

Примечание. Обычно вы хотите применять эти методы в компараторах. Потому что тогда вы можете применить свое сравнение в структуре коллекции java для сортировки массивов массивов и т. д. Поэтому я бы вместо того, чтобы возвращать логическое значение, возвращал int. В частности,

class LexicoComparator implements Comparator<ArrayList<Integer>> {
    @Override
    public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
        for(int i = 0; i < a.size() && i < b.size(); ++i) {
            int diff = a.get(i) - b.get(i);

            if (diff != 0) {
                return diff;
            }
        }

        return a.size() - b.size();
    }
}
person Skrabák Csaba    schedule 12.03.2020

arrow_upward
0
arrow_downward

// Приведенную ниже функцию можно использовать для лексикографического сравнения двух массивов.

public int lexicoSmaller(ArrayList<Integer> list1, ArrayList<Integer> list2)
{
    int n = list1.size();

    for(int i = 0; i < n; i++)
    {
        if(list1.get(i) < list2.get(i)) 
        {
            return 1; //list1 is smaller lexicographically
        }
        if(list1.get(i) > list2.get(i))
        {
            return -1; //list2 is smaller lexicographically
        }
    }
    
    return 0;  //list1 and list2 are equal
}
person Hardik singla    schedule 16.05.2021