题目分析
- 题目给出我们两个升序数组,并给出一个target值
- 题目要求我们考虑两个升序数组,两者第target个小的数字。
方法一:合并后排序
- 实现思路
-
首先将两个列表数字全部合并起来
-
然后对整个合并后的列表进行排序
-
最后直接随机访问下标为target-1的目标数字即可
-
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param arr1 int整型一维数组
# @param arr2 int整型一维数组
# @param target int整型
# @return int整型
#
class Solution:
def findKthNum(self , arr1: List[int], arr2: List[int], target: int) -> int:
# write code here
l = arr1 + arr2 #合并列表
l.sort() #排序列表
return l[target-1]
复杂度分析
- 时间复杂度:,其中分别为的长度
- 空间复杂度:,维护了一个合并的列表空间
方法二:双指针
- 实现思路
- 由于我们给出的两个列表都是升序的,因此我们要利用升序的条件,用双指针的方法进行计数
- 我们用
idx1
和idx2
表示两个列表当前访问的数字下标,并用i
进行计数 - 随着
i
计数的同时,比较两个列表中所指的数字大小,数字小的下标继续往后迭代 - 如果出现某个列表遍历到末尾,而
i
仍未计数到target
,则继续单独迭代另一个列表 - 直到计数到
target
之后,返回最后一步移动的数字下标所指的数字,我们用两个flag值f1,f2
来确定谁是最后一次访问的数字 - 最终返回下标所指数字即可
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @param arr1 int整型一维数组
# @param arr2 int整型一维数组
# @param target int整型
# @return int整型
#
class Solution:
def findKthNum(self , arr1: List[int], arr2: List[int], target: int) -> int:
# write code here
k = target
i, idx1, idx2 = 0, -1, -1
f1, f2 = 0, 0
while i < k:
if idx1+1 < len(arr1) and idx2+1 < len(arr2): # 两列表都未越界
if arr1[idx1+1] < arr2[idx2+1]: # 比较哪一个小,哪一个下标移动
idx1 += 1
f1, f2 = 1, 0
else:
idx2 += 1
f1, f2 = 0, 1
elif idx1+1 < len(arr1): # 只有列表1未越界
idx1 += 1
f1, f2 = 1, 0
else: # 只有列表2未越界
idx2 += 1
f1, f2 = 0, 1
i += 1
if f1:
return arr1[idx1]
else:
return arr2[idx2]
复杂度分析
- 时间复杂度:,因为程序思路为计数枚举的,所以最大的时间上限也只跟
target
值有关 - 空间复杂度:,只引入了常量级别的空间开销