CONY的世界

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following 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]
]

Given target = 5, return true.

Given target = 20, return false.

Success:

78 ms, beats 97.42 % of python submissions

這題一開始就想偏了，一直想說不會用類似full search 的方式做吧，然後就想說要用不斷縮小範圍來找
事實是這題根本每行的值關聯幾乎是0
因為會有像是[ [1,2,5],[2,3,7],[21,25,30] ] 這樣testcase的存在

參考作法就是判斷最後邊的值，如果比target 大，就一個一個下去比，
直到大於不成立，就可以來判斷是不是等於，如果不是等於就跳到下一行

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        j = -1
        for row in matrix:
            while j+len(row) and row[j] > target:
                j -= 1
            if row[j] == target:
                return True
        return False

215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ? k ? array's length.

Success:

42 ms, beats 86.3 % of python submissions

這題蠻簡單的，找第k大的，我是先用sort後，用python list 裡面的別的 - k，找到後面數來第k個

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        Set = sorted(nums)
        return Set[-k]