Как мне найти номер в 2d массиве, отсортированном слева направо и сверху вниз?

Ответ 1

Здесь простой подход:

1. Начните с нижнего левого угла.
2. Если цель меньше этого значения, она должна быть выше нас, поэтому поднимитесь на одну.
3. В противном случае мы знаем, что цель не может быть в этом столбце, поэтому двигайтесь вправо.
4. Перейти к 2.

Для массива NxM это выполняется в O(N+M). Я думаю, что это будет трудно сделать лучше. :)

Изменить: много хорошего обсуждения. Я говорил об общем случае выше; ясно, что если N или M малы, вы можете использовать подход бинарного поиска, чтобы сделать это во время, приближающемся к логарифмическому времени.

Вот некоторые подробности для любопытных:

история

Этот простой алгоритм называется " поиск в седле". Это было вокруг некоторое время, и это оптимально, когда N == M Некоторые ссылки:

• Дэвид Грис, Наука программирования. Springer-Verlag, 1989.
• Эдсгар Дейкстра, Седлбэк Поиск. Примечание EWD-934, 1985.

Однако, когда N < M, интуиция предполагает, что бинарный поиск должен работать лучше, чем O(N+M): например, когда N == 1, чистый бинарный поиск будет выполняться в логарифмическом, а не линейном времени.

В худшем случае

Ричард Берд исследовал эту интуицию о том, что бинарный поиск может улучшить алгоритм Saddleback в статье 2006 года:

• Ричард С. Берд, " Улучшение поиска в обратном направлении: урок в разработке алгоритмов", "Математика построения программ", с. 82--89, том 4014, 2006.

Используя довольно необычный разговорный прием, Берд показывает нам, что для N <= M эта задача имеет нижнюю границу Ω(N * log(M/N)). Эта граница имеет смысл, поскольку она дает нам линейную производительность при N == M и логарифмическую производительность при N == 1.

Алгоритмы для прямоугольных массивов

Один из подходов, использующий построчный бинарный поиск, выглядит следующим образом:

1. Начните с прямоугольного массива, где N < M. Допустим, N - строки, а M - столбцы.
2. Выполните бинарный поиск в средней строке value. Если мы найдем это, мы сделали.
3. В противном случае мы нашли соседнюю пару чисел s и g, где s < value < g.
4. Прямоугольник чисел над и слева от s меньше value, поэтому мы можем его устранить.
5. Прямоугольник ниже и справа от g больше value, поэтому мы можем его устранить.
6. Перейдите к шагу (2) для каждого из двух оставшихся прямоугольников.

С точки зрения сложности наихудшего случая, этот алгоритм делает log(M) работу, чтобы устранить половину возможных решений, а затем рекурсивно вызывает себя дважды для двух меньших проблем. Нам нужно повторить меньшую версию этого log(M) для каждой строки, но если количество строк мало по сравнению с количеством столбцов, то возможность удаления всех этих столбцов за логарифмическое время начинает приобретать смысл,

Это придает алгоритму сложность T(N,M) = log(M) + 2 * T(M/2, N/2), который, как показывает Бёрд, равен O(N * log(M/N)).

Другой подход, опубликованный Крейгом Гидни, описывает алгоритм, аналогичный описанному выше: он проверяет строку за раз, используя размер шага M/N Его анализ показывает, что это также приводит к производительности O(N * log(M/N)).

Сравнение производительности

Анализ Big-O - это хорошо, но насколько хорошо эти подходы работают на практике? В приведенной ниже таблице рассматриваются четыре алгоритма для все более "квадратных" массивов:

("Наивный" алгоритм просто ищет каждый элемент массива. "Рекурсивный" алгоритм описан выше. "Гибридный" алгоритм представляет собой реализацию алгоритма Гидни. Для каждого размера массива производительность измерялась путем синхронизации каждого алгоритма с фиксированным набором 1 000 000 случайно сгенерированных массивов.)

Некоторые заметные моменты:

• Как и ожидалось, алгоритмы "двоичного поиска" обеспечивают наилучшую производительность для прямоугольных массивов, а алгоритм Saddleback лучше всего работает для квадратных массивов.
• Алгоритм Saddleback работает хуже, чем "наивный" алгоритм для 1-мерных массивов, предположительно потому, что он выполняет множественные сравнения для каждого элемента.
• Падение производительности, которое алгоритмы "двоичного поиска" принимают для квадратных массивов, предположительно связано с накладными расходами на выполнение повторных двоичных поисков.

Резюме

Умное использование бинарного поиска может обеспечить производительность O(N * log(M/N) как для прямоугольных, так и для квадратных массивов. Алгоритм O(N + M) "обратная передача") намного проще, но страдает от снижения производительности, поскольку массивы становятся все более прямоугольными,

Ответ 2

Эта проблема занимает время Θ(b lg(t)), где b = min(w,h) и t=b/max(w,h). Я обсуждаю решение в этом сообщении в блоге.

Нижняя граница

Противник может заставить алгоритм делать запросы Ω(b lg(t)), ограничиваясь главной диагональю:

Легенда: белые ячейки - это меньшие предметы, серые ячейки - более крупные предметы, желтые ячейки - предметы с меньшим или равным, а оранжевые - больше или равно. Противник заставляет решение быть в зависимости от того, какая желтая или оранжевая ячейка выполняет запросы алгоритма.

Обратите внимание, что существуют b независимые отсортированные списки размера t, требующие от Ω(b lg(t)) запросов полностью исключить.

Алгоритм

• (не ограничивая общности, считаем, что w >= h)
• Сравните целевой объект с ячейкой t слева от верхнего правого угла допустимой области
  • Если элемент ячейки соответствует, верните текущую позицию.
  • Если элемент ячейки меньше целевого элемента, удалите оставшиеся ячейки t в строке с бинарным поиском. Если соответствующий элемент найден во время выполнения этого, верните его позицию.
  • В противном случае элемент ячейки больше целевого элемента, исключая короткие столбцы t.
• Если нет допустимой области, возвратите отказ
• Перейти к шагу 2

Поиск элемента:

Определение элемента не существует:

Легенда: белые ячейки - это меньшие элементы, серые ячейки - более крупные предметы, а зеленая ячейка - равный элемент.

Анализ

Есть короткие столбцы b*t для устранения. Для устранения существует b длинные строки. Устранение длинной строки стоит O(lg(t)) времени. Устранение коротких столбцов t стоит O(1) времени.

В худшем случае нам придется удалять каждый столбец и каждую строку, принимая время O(lg(t)*b + b*t*1/t) = O(b lg(t)).

Обратите внимание, что я принимаю lg зажима для результата выше 1 (т.е. lg(x) = log_2(max(2,x))). Поэтому, когда w=h, что означает t=1, мы получаем ожидаемую оценку O(b lg(1)) = O(b) = O(w+h).

код

public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer<T>.Default;

    // check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    // search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        // query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        // did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        // we eliminated most of the current minimum column
        // spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

Ответ 3

Я бы использовал стратегию "разделяй и властвуй" для этой проблемы, аналогично тому, что вы предлагали, но детали немного отличаются.

Это будет рекурсивный поиск по поддиапазонам матрицы.

На каждом шаге выберите элемент в середине диапазона. Если найденное значение - это то, что вы ищете, то все готово.

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

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

И ba-da-bing, вы его нашли.

Обратите внимание, что каждый рекурсивный вызов обрабатывает только текущий поддиапазон, а не (например) ВСЕ строки выше текущей позиции. Только те, которые находятся в текущем поддиапазоне.

Здесь для вас есть псевдокод:

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

Ответ 4

Два основных ответа до сих пор кажутся возможно O(log N) "ZigZag method" и O(N+M) методом двоичного поиска. Я думал, что сделаю некоторое тестирование, сравнивая два метода с некоторыми различными настройками. Вот подробности:

В каждом тесте массив равен N x N, при этом N изменяется от 125 до 8000 (самая большая моя куча JVM может обрабатывать). Для каждого размера массива я выбрал случайное место в массиве, чтобы поместить один 2. Затем я помещаю a 3 везде (справа и внизу 2), а затем заполнял остальную часть массива 1. Некоторые из более ранних комментаторов, казалось, думали, что такой тип установки приведет к наихудшему времени выполнения обоих алгоритмов. Для каждого размера массива я выбрал 100 различных случайных местоположений для 2 (цель поиска) и прошел тест. Я записал среднее время запуска и наихудшее время выполнения для каждого алгоритма. Поскольку это происходило слишком быстро, чтобы получить хорошие показания MS на Java, и, поскольку я не доверяю Java nanoTime(), я каждый раз повторял каждый тест 1000 раз, чтобы постоянно добавлять равномерный коэффициент смещения. Вот результаты:

ZigZag избивает бинарный файл в каждом тесте как в среднем, так и в худшем случае, однако все они находятся на порядок друг от друга более или менее.

Вот код Java:

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false; 
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

Ответ 5

Это краткое доказательство нижней оценки задачи.

Вы не можете сделать это лучше, чем линейное время (в терминах размеров массива, а не количества элементов). В приведенном ниже массиве каждый из элементов, обозначенных как *, может быть либо 5, либо 6 (независимо от других). Поэтому, если ваше целевое значение равно 6 (или 5), алгоритм должен изучить все из них.

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

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

Обновление: Как отметил Джеффри Л. Уитледж, он является оптимальным только как асимптотическая нижняя граница времени выполнения и размер входных данных (рассматривается как одна переменная). Время работы, рассматриваемое как функция с двумя переменными для обоих размеров массива, может быть улучшено.

Ответ 6

Я думаю Вот ответ, и он работает для любой сортированной матрицы

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

Ответ 7

Интересный вопрос. Рассмотрите эту идею - создайте одну границу, где все числа больше вашей цели, а другая, где все числа меньше вашей цели. Если что-то осталось между ними, это ваша цель.

Если я ищу 3 в вашем примере, я читаю через первую строку, пока не нажму 4, а затем найдите наименьшее соседнее число (включая диагонали) больше 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Теперь я делаю то же самое для тех чисел, которые меньше 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Теперь я спрашиваю, что-нибудь внутри двух границ? Если да, то это должно быть 3. Если нет, то нет 3. Сортировка косвенно, так как я фактически не нахожу номер, я просто выводю, что он должен быть там. У этого есть дополнительный бонус подсчета ВСЕХ 3-х.

Я попробовал это на некоторых примерах и, похоже, работает нормально.

Ответ 8

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

Ответ 9

а. Сделайте двоичный поиск на тех строках, где может быть установлен целевой номер.

В. Сделайте это графиком: найдите номер, взяв всегда самого маленького невидимого соседа node и отступая, когда найдено слишком большое число

Ответ 10

Бинарный поиск будет лучшим подходом, imo. Начиная с 1/2 x, 1/2 y сократит его пополам. IE 5x5-квадрат был бы чем-то вроде x == 2/y == 3. Я округлил одно значение вниз и одно значение до лучшей зоны в направлении целевого значения.

Для ясности следующая итерация даст вам что-то вроде x == 1/y == 2 OR x == 3/y == 5

Ответ 11

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

1 2 3
2 3 4
3 4 5

1. Поиск квадрата

Я бы использовал бинарный поиск по диагонали. Целью является определение меньшего числа, которое не строго ниже целевого числа.

Скажем, я ищу 4, например, тогда я бы остановил поиск 5 в (2,2).

Тогда я уверен, что если 4 находится в таблице, он находится в позиции либо (x,2), либо (2,x) с x в [0,2]. Ну, это всего 2 бинарных поиска.

Сложность не сложна: O(log(N)) (3 бинарных поиска в диапазонах длины N)

2. Поиск прямоугольника, наивный подход

Конечно, это становится немного сложнее, когда N и M отличаются (прямоугольником), рассмотрим этот вырожденный случай:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

И скажем, что я ищу 9... Диагональный подход по-прежнему хорош, но определение диагональных изменений. Здесь моя диагональ [1, (5 or 6), 17]. Скажем, я взял [1,5,17], тогда я знаю, что если 9 находится в таблице, то он либо находится в подчасти:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

Это дает нам 2 прямоугольника:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

Итак, мы можем рекурсировать! вероятно, начиная с единицы с меньшим количеством элементов (хотя в этом случае она убивает нас).

Я должен указать, что если одно из измерений меньше 3, мы не можем применять диагональные методы и должны использовать двоичный поиск. Здесь это означало бы:

• Применить двоичный поиск на 10 11 12 13 14 15 16, не найден
• Применить двоичный поиск на 5 6 7 8, не найден
• Применить двоичный поиск на 6 7 8 9, не найден

Это сложно, потому что для достижения хорошей производительности вы можете различать несколько случаев, в зависимости от общей формы....

3. Поиск прямоугольника, жестокого подхода

Было бы намного проще, если бы мы имели дело с квадратом... так что пусть просто квадратные вещи.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

Теперь мы имеем квадрат.

Конечно, мы, скорее всего, НЕ будем создавать эти строки, мы могли бы просто имитировать их.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

поэтому он ведет себя как квадрат, не занимая больше памяти (за счет скорости, возможно, в зависимости от кеша... о хорошо: p)

Ответ 12

EDIT:

Я неправильно понял вопрос. Как отмечают в комментариях, это работает только в более ограниченном случае.

В языке, таком как C, который хранит данные в строчном порядке, просто рассматривайте его как 1D-массив размера n * m и используйте двоичный поиск.

Ответ 13

У меня есть рекурсивное решение Divide and Conquer. Основная идея для одного шага: Мы знаем, что Left-Upper (LU) наименьший, а правый-нижний (RB) является наибольшим номером, поэтому заданное No (N) должно: N >= LU и N <= = RB

IF N == LU и N == RB:: Element Found и Abort возвращают позицию/индекс Если N >= LU и N <= RB = FALSE, No не существует и прерывается. Если N >= LU и N = RB = TRUE, разделите 2D-массив в 4 равных частях 2D-массива каждый логически.   А затем примените один и тот же шаг к всем четырем поддиапазонам.

Мое Алго правильное Я реализовал на своем компьютере друзей. Сложность: каждые 4 сравнения могут использоваться для вывода полного количества элементов на одну четвертую в худшем случае. Итак, моя сложность составляет 1 + 4 x lg (n) + 4 Но действительно ожидал, что это будет работать над O (n)

Я думаю, что что-то не так где-то в моем вычислении Сложности, пожалуйста, исправьте, если так..

Ответ 14

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    // base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    // early fails
    // array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    // arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    // arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    // arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    // alas ! i have to keep looking

    // arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        // search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    // arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

Ответ 15

Оптимальным решением является запуск в верхнем левом углу, который имеет минимальное значение. Двигайтесь по диагонали вниз вправо, пока не нажмете элемент, значение которого >= значение данного элемента. Если значение элемента равно значению для данного элемента, return будет найдено как true.

В противном случае мы можем действовать двумя способами.

Стратегия 1:

• Переместитесь в колонку и найдите данный элемент, пока мы не достигнем конца. Если найдено, возврат найден как истинный
• Двигайтесь влево в строке и ищите данный элемент, пока мы не достигнем конца. Если найдено, возврат найден как истинный
• return найден как false

Стратегия 2: Обозначим через я индекс строки, а j - индекс столбца диагонального элемента, который мы остановили. (Здесь мы имеем я = j, BTW). Пусть k = 1.

• Повторите приведенные ниже шаги, пока i-k >= 0
  • Искать, если [i-k] [j] равен данному элементу. если да, возврат найден как истинный.
  • Искать, если [i] [j-k] равен данному элементу. если да, возврат найден как истинный.
  • Приращение k

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Ответ 16

Я предлагаю хранить все символы в 2D list. затем найдите индекс требуемого элемента, если он существует в списке.

Если нет, напечатайте соответствующее сообщение еще напечатать строку и столбец как:

row = (index/total_columns) и column = (index%total_columns -1)

Это приведет к появлению только бинарного времени поиска в списке.

Пожалуйста, предложите любые исправления.:)

Ответ 17

Если O (M log (N)) решение одобрено для массива MxN -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

Рабочая демонстрация С++.

Пожалуйста, дайте мне знать, если это не сработает или если есть ошибка.

Ответ 18

Учитывая квадратную матрицу следующим образом:

[ a b c ]
[ d e f ]
[ i j k ]

Мы знаем, что a < c, d < f, я < к. Мы не знаем, является ли d < c или d > c и т.д. У нас есть гарантии только в 1-мерном виде.

Глядя на конечные элементы (c, f, k), мы можем сделать какой-то фильтр: N < c? search(): next(). Таким образом, у нас есть n итераций по строкам, причем каждая строка принимает либо O (log (n)) для двоичного поиска, либо O (1), если отфильтрована.

Позвольте мне привести пример, где N = j,

1) Проверить строку 1. j < с? (нет, идите дальше)

2) Проверьте строку 2. j < е? (да, поиск в бинах ничего не получает)

3) Проверьте строку 3. j < к? (да, поиск в бине находит его)

Повторите попытку с помощью N = q,

1) Проверить строку 1. q < с? (нет, идите дальше)

2) Проверить строку 2. q < е? (нет, идите дальше)

3) Проверить строку 3. q < к? (нет, идите дальше)

Вероятно, есть лучшее решение, но это легко объяснить..:)

Ответ 19

Поскольку это вопрос интервью, это, по-видимому, приведет к обсуждению алгоритмов Параллельное программирование и Map-reduce.

См. http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html