40.在两个长度相等的排序数组中找到上中位数

题目描述

给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。

上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数

[要求]

时间复杂度为O(logN)O(log**N)，额外空间复杂度为O(1)O(1)

输入

[1,2,3,4],[3,4,5,6]

返回值

3

说明

总共有8个数，上中位数是第4小的数，所以返回3。 

输入

[0,1,2],[3,4,5]

返回值

2

说明

总共有6个数，那么上中位数是第3小的数，所以返回2  

分析

1.刚开始我想的是用一个数组将两个数组拼接起来，然后出现各种越界问题

2.然后就使用集合来解决该问题，将两个数组的元素添加到一个集合里

3.然后对集合进行排序，然后返回中间值即可，因为下标是从0开始的，所以在返回的时候需要减一；

代码实现

  import java.util.*;
    
    
    public class Solution {
        /**
         * find median in two sorted array
         * @param arr1 int整型一维数组 the array1
         * @param arr2 int整型一维数组 the array2
         * @return int整型
         */
       public  int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
    		ArrayList list = new ArrayList<>();
    		for(int i:arr1)
    			list.add(i);
    		for(int i:arr2)
    			list.add(i);
    		Collections.sort(list);
    		return (int)list.get((list.size()/2)-1);
    		
    	}
    }