本文共 5830 字，大约阅读时间需要 19 分钟。
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例:输入:
nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3输出: [1,2,2,3,5,6]
class Solution(object): def merge(self,nums1,m,nums2,n): while n>0 and m>0: if nums1[m-1]>=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m-=1 else: nums1[m+n-1] = nums2[n-1] n-=1 if m == 0: for i in range(n): nums1[i] = nums2[i] return nums1if __name__ == "__main__": solu = Solution() print(solu.merge([1,2,3,0,0,0],3,[2,5,6],3))
方法二：
class Solution2(object): def merge(self,nums1,m,nums2,n): nums1[m:m+n] = nums2[:] nums1.sort() return nums1
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2] 示例 2:输入: nums = [1], k = 1
输出: [1] 说明：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。语法
sorted 语法： sorted(iterable[, cmp[, key[, reverse]]]) 参数说明： iterable – 可迭代对象。 cmp – 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。 key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。 reverse – 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。class Solution(object): def top_K_frequent(self,nums,k): my_dict = { } for i in nums: if i not in my_dict: my_dict[i] = 1 else: my_dict[i] += 1 fre_list = sorted(my_dict.items(),key = lambda x : x[1],reverse = True) res = [i[0] for i in fre_list] return res[:k] 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5 示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4 说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
class Solution(object): def findKthLargest(self,nums,k): nums = sorted(nums,reverse=True) return nums[k-1]if __name__ == "__main__": nums1 = [3,2,1,5,6,4] k1 = 2 nums2 = [3,2,3,1,2,4,5,5,6] k2 = 4 solu = Solution() print(solu.findKthLargest(nums1,k1)) print("---------------") print(solu.findKthLargest(nums2,k2)) 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2] 进阶：一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？基数排序，统计0，1，2各自出现的次数，重写数组就好了
在这里插入代码片
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
class Solution(object): # The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): def isBadVersion(self,x): return x def first_bad_version(self,n): begain,end = 1,n while begain < end: mid = (begain+end)//2 if self.isBadVersion(mid): end = mid else: begain = mid + 1 return begain
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]输出: 2解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2:
输入: nums = [1,2,1,3,5,6,4]输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
说明:
你的解法应该是 O(logN) 时间复杂度的。
class Solution(object): def find_peak_element(self,nums): begain,end = 0, len(nums)-1 while begain < end: mid = (begain+end)//2 if nums[mid] > nums[mid+1]: end = mid else: begain = mid + 1 return begain
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]
class Solution(object): def search_range(self,nums,target): if len(nums) == 0: return [-1,1] if target < nums[0] or target > nums[-1]: return [-1,1] l,r = 0,len(nums)-1 while l <= r: mid = (l+r)//2 if target < nums[mid]: r = mid-1 if target > nums[mid]: l = mid+1 if target == nums[mid]: l=r=mid while l-1 >= 0 and nums[l-1] == target: l -= 1 while r+1 >= len(nums)-1 and nums[r+1] == target: r += 1 return [l,r] return [-1,1]
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution(object): def merge(self,range_list): res = [] i = 0 range_list = sorted(range_list) while i < len(range_list): left = range_list[i][0] right = range_list[i][1] while i < len(range_list)-1 and range_list[i+1][1] < right: i += 1 right = max(right,range_list[i][1]) res.append([left,right]) i += 1 return res
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。 示例:现有矩阵 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(object): def search_matrix(self,matrix,target): if matrix == None: return False for i in matrix: if target in i: return True return Falseif __name__ == "__main__": m =[ [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]] target1 = 5 target2 = 20 solu = Solution() print(solu.search_matrix(m,target1)) print(solu.search_matrix(m, target2))
转载地址：http://oluib.baihongyu.com/