0

Задача следующая:

Дается двумерный массив, нужно вернуть первую строку,в которой все элементы ни разу не встречаются в массиве.

Пример:

[ [10, 2, 3], [-1, 4, 5], [6, 10, 1] ] -> вернет строку 1

Написал код, используя множество HashSet. Для данного примера метод работает, но к примеру для массива : [ [12, 2, 3], [-1, 4, 5], [6, 10, 1]] -> возвращает строку 2, хотя должна быть 0.

Фрагмент кода:

static int findUniqueRow(int[][] array) {
    HashSet<Integer> set = new HashSet<>();
    int index = -1;
    for (int i = 0; i < array.length; i++) {

        for (int j = 0; j < array[i].length; j++) {
            if (!set.contains(array[i][j])) {
                set.add(array[i][j]);
            } else return index;
        }
        index = i;
    }
    return index;
}
0

2 ответа 2

1

для небольшого набора данных это разницы не имеет, но если, например, важна скорость, но не важна память, можно сделать как то так

static int findUniqueRow(int[][] array) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            int k = array[i][j];
            if (map.containsKey(k)) map.put(k, map.get(k) + 1);
            else map.put(k, 1);
        }
    }
    HashMap<Integer, Integer> line = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        line.clear();
        for (int j = 0; j < array[i].length; j++) {
            int k = array[i][j];
            if (line.containsKey(k)) line.put(k, line.get(k) + 1);
            else line.put(k, 1);
        }

        boolean match = true;
        for (int key : line.keySet()) {
            if (line.get(key) != map.get(key)) {
                match = false;
                break;
            }
        }
        if (match) return i;
    }
    return -1;
}
1

Код работает не верно! он не проверяет уникальность строк между собой, а уникальность каждого элемента в массиве! В первом вернет один потому что когда цикл дойдет до 10 в 3 ряду, то вернет index который равен 1. Во втором случае цикл завершает свою работу, потому что в массиве все элементы уникальны.

static int findUniqueRow(int[][] array) {
    for (int i = 0; i < array.length; i++) {
        boolean isUnique = true;
        for (int j = 0; j < array[i].length && isUnique; j++) {
            for (int k = 0; k < array.length && isUnique; k++) {
                if (k == i) {
                    continue;
                }
                for (int v = 0; v < array[k].length; v++) {
                    if (array[i][j] == array[k][v]) {
                        isUnique = false;
                        break;
                    }
                }
            }
        }
        if (isUnique) {
            return i;
        }
    }
    return -1;
}

Наверно можно было сделать и красивей, однозначно можно было бы исключать строки с найденими не уникальными элементами и не проверять их каждый раз - но и так сойдет) ... для массива 3х3

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.