题目主要信息

给定两个升序的数列 arr1 和 arr2 ，和一个整数 target ，请你找出两个数列中第 target 小的值。

方法一：合并+直接返回

具体方法

由于arr1和arr2都是升序的，可以将两个数组都存入一个temp中，返回的是第target小的值，由于temp从0开始，所以最后直接返回temp.get(target-1)的数即可。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findKthNum (int[] arr1, int[] arr2, int target) {
        // write code here
              // write code here
        List<Integer> temp = new ArrayList<>();
        int len1 = arr1.length,len2 = arr2.length;
        int i = 0,j = 0;
      // 两者都满足索引大小
        while(i<len1 && j < len2){
          // arr1小
            if(arr1[i]<arr2[j]){
                temp.add(arr1[i]);
                i++;
            }else{
                temp.add(arr2[j]);
                j++;
            }
        }
      // 如果i没遍历完
        while(i<len1){
            temp.add(arr1[i]);
            i++;
        }
      // 如果j没遍历完
        while(j<len2){
            temp.add(arr2[j]);
            j++;
        }
        return temp.get(target-1);
    }
}

复杂度分析

• 时间复杂度：$O(m+n)O(m+n)$,需要遍历两个数组
• 空间复杂度：$O(m+n)O(m+n)$,存储两个数组的元素的temp。

方法二：双指针

具体方法

使用双指针i和j，i标记arr1的索引位置，j标记arr2的索引位置。

根据两个数组的大小求出target，执行target次循环，在每一轮将较小的赋值结果。

跟方法一类似，这里不用temp数组了，而是用一个临时遍历result。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int findKthNum (int[] arr1, int[] arr2, int target) {
        // write code her

        int len1 = arr1.length,len2 = arr2.length;
        //循环target次，每次将较小的值赋值给result，最后result一定是第K小的数
        int result = 0;
        int i =0,j = 0;
        while(target-->0){
            //如果i和j都没有到末尾
            if(i < len1 && j<len2){
                //将两者中较小的赋值给res，并后移游标
                if(arr1[i]<arr2[j]){
                    result = arr1[i++];
                }
                else{
                    result = arr2[j++];
                }
            }
            //如果i到达末尾，则继续将arr2数组的值赋值给res
            else if(i == len1){
                result = arr2[j++];
            }
            //否则，将arr1数组的值赋值给res
            else{
                result = arr1[i++];
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(K)O(K)$,需要给result赋值target次，循环总共执行target次，$O\mathrm{（}target\mathrm{）}O（target）$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。