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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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