26

これはインタビューの質問です。

行と列が並べ替えられた行列で、K番目に小さい要素を見つけます。K番目 に小さい要素はなどのいずれかで
あるというのは正しいですか?a[i, j]i + j = K

4

9 に答える 9

42

間違い。

次のような単純な行列を考えてみましょう。

1 3 5
2 4 6
7 8 9

9 は最大 (9 番目に小さい) 要素です。しかし、9 は A[3, 3] にあり、3+3 != 9 です (どのようなインデックス規則を使用しても、真になることはありません)。

行を段階的にマージし、最小要素を効率的に見つけるためにヒープを追加することで、この問題を O(k log n) 時間で解決できます。

基本的に、最初の列の要素をヒープに入れ、元の行を追跡します。各ステップで、ヒープから最小要素を削除し、元の行から次の要素をプッシュします (行の最後に到達した場合は、何もプッシュしません)。最小値の削除と新しい要素の追加の両方に O(log n) のコストがかかります。j 番目のステップで4j番目に小さい要素を削除するため、kステップの後、操作の総コストが計算されますO(k log n) (n は行列の行数)。

上記のマトリックスの場合、最初1,2,7はヒープから始めます。を削除1して追加します3(最初の行は である1 3 5ため) を取得します2,3,7。を削除2して追加すると、4が得られます3,4,7。削除3して追加5して取得します4,5,7。削除4して追加6して取得します5,6,7。グローバルにソートされた順序で要素を削除していることに注意してください。このプロセスを続けるとk、k 回の反復後に 4 番目に小さい要素が得られることがわかります。

(行列の行数が列数よりも多い場合は、代わりに列を操作して実行時間を短縮します。)

于 2013-03-02T21:28:23.133 に答える
33

O(k log(k))解決。

  • 最小ヒープを構築します。

  • (0,0)ヒープに追加します。最小の要素が見つからない場合は、ヒープからkth一番上の要素を削除し、次の 2 つの要素を(x,y)追加します。[(x+1,y)(x,y+1)]

O(k)サイズのヒープに対して操作を行っているO(k)ため、複雑になっています。

于 2013-09-23T18:18:50.393 に答える
0

人々が前に述べたように、最も簡単な方法はmin heap. PriorityQueue を使用した Java 実装を次に示します。

private int kthSmallestUsingHeap(int[][] matrix, int k) {

    int n = matrix.length;

    // This is not necessary since this is the default Int comparator behavior
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    };

    // building a minHeap
    PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pq.add(matrix[i][j]);
        }
    }

    int ans = -1;
    // remove the min element k times
    for (int i = 0; i < k; i++) {
        ans = pq.poll();
    }

    return ans;
}
于 2016-09-16T20:25:30.703 に答える
-1 
//int arr[][] = {{1, 5, 10, 14},
//        {2, 7, 12, 16},
//        {4, 10, 15, 20},
//        {6, 13, 19, 22}
//};
// O(k) Solution
public static int myKthElement(int arr[][], int k) {
    int lRow = 1;
    int lCol = 0;
    int rRow = 0;
    int rCol = 1;
    int count = 1;

    int row = 0;
    int col = 0;

    if (k == 1) {
        return arr[row][col];
    }

    int n = arr.length;
    if (k > n * n) {
        return -1;
    }

    while (count < k) {
        count++;

        if (arr[lRow][lCol] < arr[rRow][rCol]) {
            row = lRow;
            col = lCol;

            if (lRow < n - 1) {
                lRow++;
            } else {
                if (lCol < n - 1) {
                    lCol++;
                }

                if (rRow < n - 1) {
                    lRow = rRow + 1;
                }
            }
        } else {
            row = rRow;
            col = rCol;

            if (rCol < n - 1) {
                rCol++;
            } else {
                if (rRow < n - 1) {
                    rRow++;
                }
                if (lCol < n - 1) {
                    rCol = lCol + 1;
                }
            }
        }
    }

    return arr[row][col];
}
于 2017-03-22T05:33:01.233 に答える