Skip to content

Latest commit

 

History

History
87 lines (56 loc) · 3.28 KB

06.02.01-Exercises.md

File metadata and controls

87 lines (56 loc) · 3.28 KB

06.02.01 练习题目(第 05 天)

1.1 题目大意

描述:给定一个整数数组 nums,数组中值互不相同。给定的 nums 是经过升序排列后的又进行了「旋转」操作的。再给定一个整数 target

要求:从 nums 中找到 target 所在位置,如果找到,则返回对应下标,找不到则返回 -1

说明

  • 旋转操作:升序排列的数组 nums 在预先未知的第 k 个位置进行了右移操作,变成了 [nums[k]], nums[k+1], ... , nums[n-1], ... , nums[0], nums[1], ... , nums[k-1]

示例

输入nums = [4,5,6,7,0,1,2], target = 0
输出4


输入nums = [4,5,6,7,0,1,2], target = 3
输出-1

2.1 题目大意

描述:给定一个整数数组 nums

要求:找到峰值元素并返回其索引。必须实现时间复杂度为 $O(\log n)$ 的算法来解决此问题。

说明

  • 峰值元素:指其值严格大于左右相邻值的元素。
  • 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
  • 可以假设 $nums[-1] = nums[n] = -∞$
  • $1 \le nums.length \le 1000$
  • $-2^{31} \le nums[i] \le 2^{31} - 1$
  • 对于所有有效的 $i$ 都有 $nums[i] != nums[i + 1]$

示例

输入nums = [1,2,3,1]
输出2
解释3 是峰值元素你的函数应该返回其索引 2输入nums = [1,2,1,3,5,6,4]
输出1  5 
解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5其峰值元素为 6

3.1 题目大意

描述:给定两个正序(从小到大排序)数组 nums1nums2

要求:找出并返回这两个正序数组的中位数。

说明

  • 算法的时间复杂度应该为 $O(\log (m + n))$
  • $nums1.length == m$
  • $nums2.length == n$
  • $0 \le m \le 1000$
  • $0 \le n \le 1000$
  • $1 \le m + n \le 2000$
  • $-10^6 \le nums1[i], nums2[i] \le 10^6$

示例

输入nums1 = [1,2], nums2 = [3,4]
输出2.50000
解释合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

习题解析

  1. 0033. 搜索旋转排序数组」习题解析:网页链接Github 链接
  2. 0162. 寻找峰值」习题解析:网页链接Github 链接
  3. 0004. 寻找两个正序数组的中位数」习题解析:网页链接Github 链接