题目分析

  1. 题目给出我们两个升序数组,并给出一个target值
  2. 题目要求我们考虑两个升序数组,两者第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]

复杂度分析

  • 时间复杂度:O((l1+l2)log(l1+l2))O((l1+l2)log(l1+l2)),其中l1,l2l1,l2分别为arr1,arr2arr1,arr2的长度
  • 空间复杂度:O(l1+l2)O(l1+l2),维护了一个合并的列表空间

方法二:双指针

  • 实现思路
    • 由于我们给出的两个列表都是升序的,因此我们要利用升序的条件,用双指针的方法进行计数
    • 我们用idx1idx2表示两个列表当前访问的数字下标,并用i进行计数
    • 随着i计数的同时,比较两个列表中所指的数字大小,数字小的下标继续往后迭代
    • 如果出现某个列表遍历到末尾,而i仍未计数到target,则继续单独迭代另一个列表
    • 直到计数到target之后,返回最后一步移动的数字下标所指的数字,我们用两个flag值f1,f2来确定谁是最后一次访问的数字
    • 最终返回下标所指数字即可

alt

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @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]

复杂度分析

  • 时间复杂度:O(target)O(target),因为程序思路为计数枚举的,所以最大的时间上限也只跟target值有关
  • 空间复杂度:O(1)O(1),只引入了常量级别的空间开销