房地产交易网站,展台设计搭建服务,四川省建设厅官方网站首页,网站后台信息维护要怎么做63、搜索插入位置
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5
输…63、搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5
输出: 2
示例 2:
输入: nums [1,3,5,6], target 2
输出: 1
示例 3:
输入: nums [1,3,5,6], target 7
输出: 4
提示:
1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104
思路解答
1、采用二分查找
使用两个指针left和right来表示当前搜索范围的左右边界。在每次迭代中我们计算中间元素的索引mid并将目标值与中间元素进行比较。
如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素小于目标值则更新left为mid 1继续在右半部分搜索。如果中间元素大于目标值则更新right为mid - 1继续在左半部分搜索。
最终当left right时表示搜索范围为空此时left即为目标值应该插入的位置。
def searchInsert(nums: list[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:left mid 1elif nums[mid] target:right mid - 1else:return midreturn left
64、搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
示例 1 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3
输出true
示例 2 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13
输出false
提示
m matrix.lengthn matrix[i].length1 m, n 100-104 matrix[i][j], target 104
思路解答同题21
从矩阵的右上角开始如果目标值等于当前位置的值则返回True。如果目标值大于当前位置的值则目标值一定在当前位置的下方或左方因为当前位置向左和向下都是递增的。如果目标值小于当前位置的值则目标值一定在当前位置的左上方因为当前位置向上和向右都是递增的。重复上述步骤直到找到目标值或者搜索完整个矩阵。
def searchMatrix(matrix: list[list[int]], target: int) - bool:if not matrix or not matrix[0]:return Falserows, cols len(matrix), len(matrix[0])row, col 0, cols - 1while row rows and col 0:if matrix[row][col] target:return Trueelif matrix[row][col] target:row 1else:col - 1return False
65、在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]
示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]
示例 3
输入nums [], target 0
输出[-1,-1]
提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109
思路解答
1、定义了两个辅助函数find_first和find_last来分别查找目标值的起始位置和结束位置
find_first函数找到第一个大于等于目标值的位置。find_last函数找到最后一个小于等于目标值的位置。
2、如果起始位置小于等于结束位置则返回起始位置和结束位置否则返回[-1, -1]表示目标值不存在于数组中。
def searchRange(nums: list[int], target: int) - list[int]:def find_first(nums, target):left, right 0, len(nums) - 1while left right:mid (right left) // 2if nums[mid] target:left mid 1else:right mid - 1return leftdef find_last(nums, target):left, right 0, len(nums) - 1while left right:mid (right left) // 2if nums[mid] target:left mid 1else:right mid - 1return rightstart find_first(nums, target)end find_last(nums, target)if start end:return [start, end]else:return [-1, -1]
66、搜索旋转排序数组
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4
示例 2
输入nums [4,5,6,7,0,1,2], target 3
输出-1
示例 3
输入nums [1], target 0
输出-1
提示
1 nums.length 5000-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104
思路解答
初始化左指针 left 和右指针 right分别指向数组的起始位置和结束位置。在一个循环中不断将中间位置 mid 计算为 (left right) // 2。如果 nums[mid] target表示找到了目标值直接返回 mid。接下来判断左半部分是否有序即 nums[left] nums[mid]如果是有序的就根据目标值是否在有序部分内来更新左右指针如果左半部分无序则根据目标值是否在右半部分有序部分内来更新左右指针。不断循环直到 left right表示没有找到目标值返回 -1。
def search(nums: list[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:return midif nums[left] nums[mid]: # 左半部分有序if nums[left] target nums[mid]:right mid - 1else:left mid 1else: # 右半部分有序if nums[mid] target nums[right]:left mid 1else:right mid - 1return -1
67、寻找旋转排序数组中的最小值
已知一个长度为 n的数组预先按照升序排列经由 1到 n 次 旋转后得到输入数组。例如原数组
nums [0,1,2,4,5,6,7]
在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [3,4,5,1,2]
输出1
解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。
示例 2
输入nums [4,5,6,7,0,1,2]
输出0
解释原数组为 [0,1,2,4,5,6,7] 旋转 3 次得到输入数组。
示例 3
输入nums [11,13,15,17]
输出11
解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。
提示
n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转
思路解答
初始化左指针 left 指向数组开头右指针 right 指向数组末尾。在每一步中计算中间元素的索引 mid (right left) // 2。检查中间元素 nums[mid] 与最右边元素 nums[right] 的大小关系 如果 nums[mid] nums[right]说明右半部分是有序的最小元素可能在左半部分因此将 right 移动到 mid。如果 nums[mid] nums[right]说明右半部分是无序的最小元素一定在右半部分因此将 left 移动到 mid 1。 重复步骤 2 和步骤 3直到 left 和 right 相遇此时找到了最小元素。
def findMin(nums: list[int]) - int:left, right 0, len(nums) - 1while left right:mid (right left) // 2if nums[mid] nums[right]: # 右半部分有序最小值在左半部分或者就是当前位置right midelse: # 右半部分无序最小值在右半部分left mid 1return nums[left]
68、寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1
输入nums1 [1,3], nums2 [2]
输出2.00000
解释合并数组 [1,2,3] 中位数 2
示例 2
输入nums1 [1,2], nums2 [3,4]
输出2.50000
解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5
提示
nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106
思路解答
如果第一个数组的长度大于第二个数组的长度则交换两个数组。初始化一个极大值变量infinty并分别获取两个数组的长度。初始化left和right分别指向第一个数组的起始和结束位置median1和median2初始化为0。在left小于等于right的循环内计算i和j其中i表示第一个数组的分割点j表示第二个数组的分割点。根据i和j获取四个数值nums_im1、nums_i、nums_jm1、nums_j分别表示两个数组中的前一部分的最大值和后一部分的最小值。如果nums_im1小于等于nums_j则更新median1和median2的值并将left更新为i 1否则将right更新为i - 1。循环结束后根据两个数组的总长度是奇数还是偶数返回中位数的值。
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) - float:if len(nums1) len(nums2):return findMedianSortedArrays(nums2, nums1)infinty 2 ** 40m, n len(nums1), len(nums2)left, right 0, m# median1前一部分的最大值# median2后一部分的最小值median1, median2 0, 0while left right:# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]# // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]i (left right) // 2j (m n 1) // 2 - i# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]nums_im1 (-infinty if i 0 else nums1[i - 1])nums_i (infinty if i m else nums1[i])nums_jm1 (-infinty if j 0 else nums2[j - 1])nums_j (infinty if j n else nums2[j])if nums_im1 nums_j:median1, median2 max(nums_im1, nums_jm1), min(nums_i, nums_j)left i 1else:right i - 1return (median1 median2) / 2 if (m n) % 2 0 else median1
