Leetcode - Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/

[
  [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]
]

Use binary search from up to bottom to narrow down the row.  And then run binary search in each row to find the num.

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) ==  0 || len(matrix[0]) == 0 {
        return false
    }
    if target < matrix[0][0] || target > matrix[len(matrix)-1][len(matrix[len(matrix)-1])-1] {
        return false
    }
    column := searchColumn(matrix, target)
    fmt.Println("column: ", column)
    for i := 0; i < column+1; i++ {
        result := searchRow(matrix[i], target)
        if result {
            return true
        }
    }
    
    return false
}

func searchRow(num []int, target int) bool {
    left := 0
    right := len(num)
    var mid int
    for left < right {
        mid = left + (right - left)/2
        if num[mid] == target {
            return true
        }
        if num[mid] < target {
            left = mid + 1
        }
        if num[mid] > target {
            right = mid - 1
        }
    }
    if left >= 0 && left < len(num) && left == right && num[left] == target {
        return true
    }
    return false
}

func searchColumn(matrix [][]int, target int) int {
    up := 0
    down := len(matrix)
    var mid int
    for up < down {
        mid = up + (down - up)/2
        if matrix[mid][0] == target {
            fmt.Println("find")
            return mid + 1
        }
        if matrix[mid][0] > target {
            down = mid - 1
        }
        if matrix[mid][0] < target {
            up = mid + 1
        }
    }

    if mid + 1 < len(matrix) && matrix[mid][0] <= target {
        return mid + 1
    }
    return mid
}

# @param {Integer[][]} matrix
# @param {Integer} target
# @return {Boolean}
def search_matrix(matrix, target)
    return false if matrix.length == 0 || matrix[0].length == 0
    return false if target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]
    
    row = search_row(matrix, target)
    for i in 0..row
        column = search_column(matrix[i], target)
        return true if matrix[i][column] == target
    end
    return false
end


def search_column(nums, target)

    left = 0
    right = nums.length - 1
    while left < right
        mid = left + (right - left)/2
        if nums[mid] == target
            return mid
        end

        if nums[mid] < target
            left = mid + 1
        else
            right = mid - 1
        end
    end
    return left
end


def search_row(matrix, target)
    up = 0
    down = matrix.length - 1
    mid = 0
    while up < down
      mid = up + (down - up)/2
      if matrix[mid][0] == target
        return mid + 1
      end
      if matrix[mid][0] > target
        down = mid - 1
      end
      if matrix[mid][0] < target
        up = mid + 1
      end
    end
    if (mid+1 <  matrix.length) && (matrix[mid][0] <= target)
      return mid + 1
    end
    return mid
end

• 相关文章
• 全局相关文章