劍指 Offer 04. 二維數(shù)組中的查找

在一個 n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個高效的函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
現(xiàn)有矩陣 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

給定 target = 5，返回 true。

給定 target = 20，返回 false。

方法一：暴力

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

復雜度分析：

• 時間復雜度：O(nm)O(nm)。二維數(shù)組中的每個元素都被遍歷，因此時間復雜度為二維數(shù)組的大小。
• 空間復雜度：O(1)O(1)。

方法二：遍歷

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix==null || matrix.length==0 || matrix[0].length ==0){
            return false;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0){
            int num = matrix[row][column];
            if (num == target)
                return true;
            else if (num < target)
                row++;
            else if (num > target)
                column--;
        }
        return false;
    }
}

復雜度分析

• 時間復雜度：O(n+m)O(n+m)。訪問到的下標的行最多增加 n 次，列最多減少 m 次，因此循環(huán)體最多執(zhí)行 n + m 次。
• 空間復雜度：O(1)O(1)。

劍指 Offer 11. 旋轉數(shù)組的最小數(shù)字

把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。

給你一個可能存在 重復 元素值的數(shù)組 numbers ，它原來是一個升序排列的數(shù)組，并按上述情形進行了一次旋轉。請返回旋轉數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一次旋轉，該數(shù)組的最小值為 1。

注意，數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉一次 的結果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：
輸入：numbers = [3,4,5,1,2]
輸出：1

示例 2：
輸入：numbers = [2,2,2,0,1]
輸出：0

方法一：暴力

class Solution {
    public int minArray(int[] numbers) {
        int n = Integer.MAX_VALUE;
        for(int i=0;i<numbers.length;i++){
            if (numbers[i]<n){
                n=numbers[i];
            }
        }
        return n;
    }
}

方法二：二分查找

class Solution {
    public int minArray(int[] numbers) {
        if (numbers.length==0) return numbers[0];
        int low = 0, high = numbers.length-1;
        while (low < high){
            int mid = low + (high - low) / 2;
            if (numbers[mid] < numbers[high]){
                high = mid;
            }
            else if (numbers[mid] > numbers[high]){
                low = mid + 1;
            }
            else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}

復雜度分析

• 時間復雜度：平均時間復雜度為 O(\log n)O(logn)，其中 nn 是數(shù)組 \it numbersnumbers 的長度。如果數(shù)組是隨機生成的，那么數(shù)組中包含相同元素的概率很低，在二分查找的過程中，大部分情況都會忽略一半的區(qū)間。而在最壞情況下，如果數(shù)組中的元素完全相同，那么 \texttt{while}while 循環(huán)就需要執(zhí)行 nn 次，每次忽略區(qū)間的右端點，時間復雜度為 O(n)O(n)。

• 空間復雜度：O(1)O(1)。

劍指 Offer 50. 第一個只出現(xiàn)一次的字符

在字符串 s 中找出第一個只出現(xiàn)一次的字符。如果沒有，返回一個單空格。 s 只包含小寫字母。

示例 1:
輸入：s = "abaccdeff"
輸出：'b'

示例 2:
輸入：s = "" 
輸出：' '

class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Integer> map = new HashMap<>();
        for (int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        for (int i=0;i<s.length();i++){
            if (map.get(s.charAt(i))==1){
                return s.charAt(i);
            }
        }
        return ' ';
    }
}

復雜度分析

• 時間復雜度：O(n)O(n)，其中 nn 是字符串 ss 的長度。我們需要進行兩次遍歷。
• 空間復雜度：O(∣Σ∣)，其中 Σ 是字符集，在本題中 s 只包含小寫字母，因此∣Σ∣≤26。我們需要 O(∣Σ∣) 的空間存儲哈希映射。

Java HashMap getOrDefault() 方法

hashmap.getOrDefault(Object key, V defaultValue)
參數(shù)說明：

• key - 鍵
• defaultValue - 當指定的key并不存在映射關系中，則返回的該默認值

返回值:

• 返回 key 相映射的的 value，如果給定的 key 在映射關系中找不到，則返回指定的默認值。