LeetCode.944-删除列保證排序(Delete Columns to Make Sorted)

這是悅樂書的第362次更新，第389篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第224題（順位題号是944）。我們給出了一個N個小寫字母串的數組A，它們的長度都相同。

現在，我們可以選擇任何一組删除索引，對于每個字元串，我們删除這些索引中的所有字元。

例如，如果我們有一個數組

A = [“abcdef”，“uvwxyz”]

和删除索引

{0,2,3}

，那麼删除後的數組變成了

[“bef”，“vyz”]

，縱向上看，每一列是

[“b”，“v”]

，

[“e”，“y”]

和

[“f”，“z”]

。（形式上，第c列是

[A[0][c]

A[1][c]

，...，

A[A.length-1][c]]

。）

假設我們選擇了一組删除索引

D

，使得在删除之後，A中的每個剩餘列都處于遞增排序順序。傳回

D.length

的最小可能值。例如：

輸入：[“cba”，“daf”，“ghi”]

輸出：1

說明：在選擇

D = {1}

之後，每列

[“c”，“d”，“g”]

[“a”，“f”，“i”]

處于遞增的排序順序。如果我們選擇

D = {}

，則列

[“b”，“a”，“h”]

将不是遞增排序順序。

輸入：[“a”，“b”]

輸出：0

說明：D = {}

輸入：[“zyx”，“wvu”，“tsr”]

輸出：3

說明：D = {0,1,2}

注意：

• 1 <= A.length <= 100
• 1 <= A[i].length <= 1000

02 第一種解法

題目的意思是A中包含了許多長度一樣的字元串元素，從縱向來看，單個字元串中的每一列字元大小關系需要是遞增的，如果不是，則需要删除，問需要删除多少列字元，才能保證所有列的字元大小關系都是遞增的。結合給的示例來看，

[“cba”，“daf”，“ghi”]

，縱向來看就變成了下面這樣：

cba -->  c b a
daf -->  d a f
ghi -->  g h i
           

第一列為

cdg

，是遞增的，不用删除，第二列為

bah

，不是遞增，需要删除，第三列是

afi

，是遞增的，不用删除，是以最後需要删除中間那列的字元，就能保證所有列的字元大小關系都是遞增的，是以傳回1。

思路：根據上面我們的分析，直接上兩層循環就行，外層控制列數，内層控制行數，注意下标不能越界。

此解法的時間複雜度為

O(A)

A

為數組A中所有字元的個數，空間複雜度為

O(1)

。

public int minDeletionSize(String[] A) {
    int n = A[0].length(), len = A.length;
    int count = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<len-1; j++) {
            if (A[j].charAt(i) > A[j+1].charAt(i)) {
                count++;
                break;
            }
        }
    }
    return count;
}
           

03 第二種解法

我們還可以使用二維數組來解題。

在第一種解法中，通過縱向觀察，可以将A中的所有字元看成是一個二維數組，行是A中元素個數，列是A中單個字元串的長度，先将字元初始化進二維數組中，然後周遊二維數組，比較列上前後字元的大小關系，需要删除（前後不是遞增順序）就計數加1，最後傳回累加的

count

此解法的時間複雜度時

O(A)

A

O(N*M)

N

為數組

A

的長度，

M

為

A

中單個元素的長度。

public int minDeletionSize2(String[] A) {
    int row = A.length, col = A[0].length();
    char[][] arr = new char[row][col];
    for (int i=0; i<A.length; i++) {
        arr[i] = A[i].toCharArray();
    }
    int count = 0;
    for (int i=0; i<col; i++) {
        for (int j=0; j<row-1; j++) {
            if (arr[j][i] > arr[j+1][i]) {
                count++;
                break;
            }
        }
    }
    return count;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章230+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！