本文共 1186 字，大约阅读时间需要 3 分钟。

所谓分治就是把整个问题分成无关紧要的小问题

1. 划分问题：整个问题划分成多个无关联的子问题。
2. 递归求解：递归调用求解各个子问题。
3. 合并问题：合并子问题的解，形成原始问题的解

169.求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

• 示例 1:

  输入: [3,2,3]
  输出: 3

• 示例 2:

  输入: [2,2,1,1,1,2,2]
  输出: 2

• 代码

class Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        nums.sort()        return nums[len(nums)//2]

240.搜索二维矩阵

编写一个高效的算法来搜索m x n矩阵matrix中的一个目标值target。该矩阵具有以下特性：每行的元素从左到右升序排列，每列的元素从上到下升序排列。

• 示例:

  [
  [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:    def searchMatrix(self, matrix, target):        if not matrix: return False  # 为空返回false        row, col, width = len(matrix) - 1, 0, len(matrix[0])        while row >= 0 and col < width:            if matrix[row][col] == target:  # 找到 返回true                return True            elif matrix[row][col] > target:                row = row - 1  # 进入上一行            else:                col = col + 1  # 进行右一列        return False  # 没找到 返回false

转载地址：http://ewjmf.baihongyu.com/