NC36在两个长度相等的排序数组中找到上中位数（四种语言+视频讲解）

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404f?tab=answerKey

-3、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>&amp; arr1, vector<int>&amp; arr2) {
        // write code here
        if(arr1.size() == 1) return min(arr1[0],arr2[0]);///特判
        int n = arr1.size();///数组长度
        int l1 = 0,r1 = n -1 ,l2 = 0,r2 = n -1;///初始指针
        ///元素个数位奇数，flag = 1，为偶数flag =0
        int flag = ((r1 - l1 + 1) &amp; 1);
        while(l1 &lt; r1){

            int mid1 = l1 + ((r1 - l1) &gt;&gt; 1);
            int mid2 = l2 + ((r2 - l2) &gt;&gt; 1);
            ///更新区域的个数，奇数，flag = 1，为偶数flag =0
            flag = ((r1 - l1 + 1) &amp; 1);
            ///若两数组中位数相等，整体的中位数也是这个
            if(arr1[mid1] == arr2[mid2]) return arr1[mid1];
            else if(arr1[mid1] &gt; arr2[mid2]){
                ///如果区域个数是奇数
                if(flag){
                    r1 = mid1;
                    l2 = mid2;
                }else{
                ///如果区域个数是偶数
                    r1 = mid1;
                    l2 = mid2 + 1;
                }

            }else{
                ///如果区域个数是奇数
                if(flag){
                    l1 = mid1;
                    r2 = mid2;

                }else{
                    ///如果区域个数是偶数
                    l1 = mid1 + 1;
                    r2 = mid2;
                }
            }

        }

        return min(arr1[l1],arr2[l2]);

    }
};

Java版本：

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) {
        // write code here
        if(arr1.length == 1) return Math.min(arr1[0],arr2[0]);///特判
        int n = arr1.length;///数组长度
        int l1 = 0,r1 = n -1 ,l2 = 0,r2 = n -1;///初始指针
        ///元素个数位奇数，flag = 1，为偶数flag =0
        int flag = ((r1 - l1 + 1) & 1);
        while(l1 < r1){

            int mid1 = l1 + ((r1 - l1) >> 1);
            int mid2 = l2 + ((r2 - l2) >> 1);
            ///更新区域的个数，奇数，flag = 1，为偶数flag =0
            flag = ((r1 - l1 + 1) & 1);
            ///若两数组中位数相等，整体的中位数也是这个
            if(arr1[mid1] == arr2[mid2]) return arr1[mid1];
            else if(arr1[mid1] > arr2[mid2]){
                ///如果区域个数是奇数
                if(flag==1){
                    r1 = mid1;
                    l2 = mid2;
                }else{
                ///如果区域个数是偶数
                    r1 = mid1;
                    l2 = mid2 + 1;
                }

            }else{
                ///如果区域个数是奇数
                if(flag==1){
                    l1 = mid1;
                    r2 = mid2;

                }else{
                    ///如果区域个数是偶数
                    l1 = mid1 + 1;
                    r2 = mid2;
                }
            }

        }

        return Math.min(arr1[l1],arr2[l2]);

    }
}

Python版本:

#
# find median in two sorted array
# @param arr1 int整型一维数组 the array1
# @param arr2 int整型一维数组 the array2
# @return int整型
#
class Solution:
    def findMedianinTwoSortedAray(self , arr1 , arr2 ):
        # write code here
        if(len(arr1) == 1):return min(arr1[0],arr2[0])#特判
        n = len(arr1) #数组长度
        l1,r1,l2,r2 = 0,n-1,0,n-1#初始指针
        while l1 < r1:
            mid1 = l1 + ((r1 - l1) >> 1)
            mid2 = l2 + ((r2 - l2) >> 1)
            #更新区域的个数，奇数，flag = 1，为偶数flag =0
            flag = ((r1 - l1 + 1) & 1)
            #若两数组中位数相等，整体的中位数也是这个
            if(arr1[mid1] == arr2[mid2]): return arr1[mid1]
            elif (arr1[mid1] > arr2[mid2]):
                #如果区域个数是奇数
                if flag:
                    r1 = mid1
                    l2 = mid2
                else:
                    #如果区域个数是偶数
                    r1 = mid1
                    l2 = mid2 + 1
            else:
            #如果区域个数是奇数
                if flag:
                    l1 = mid1
                    r2 = mid2
                else:
                #如果区域个数是偶数
                    l1 = mid1 + 1
                    r2 = mid2

        return min(arr1[l1],arr2[l2])

JavaScript版本:

```
/**

• find median in two sorted array

• @param arr1 int整型一维数组 the array1

• @param arr2 int整型一维数组 the array2

• @return int整型

• /
  function findMedianinTwoSortedAray( arr1 , arr2 ) {
  // write code here
  if(arr1.length == 1) return Math.min(arr1[0],arr2[0]);///特判

    let n = arr1.length;///数组长度
    let l1 = 0,r1 = n -1 ,l2 = 0,r2 = n -1;///初始指针
    ///元素个数位奇数，flag = 1，为偶数flag =0
    let flag = ((r1 - l1 + 1) & 1);
    while(l1 < r1){
  
        let mid1 = l1 + ((r1 - l1) >> 1);
        let mid2 = l2 + ((r2 - l2) >> 1);
        ///更新区域的个数，奇数，flag = 1，为偶数flag =0
        flag = ((r1 - l1 + 1) & 1);
        ///若两数组中位数相等，整体的中位数也是这个
        if(arr1[mid1] == arr2[mid2]) return arr1[mid1];
        else if(arr1[mid1] > arr2[mid2]){
            ///如果区域个数是奇数
            if(flag==1){
                r1 = mid1;
                l2 = mid2;
            }else{
            ///如果区域个数是偶数
                r1 = mid1;
                l2 = mid2 + 1;
            }
  
        }else{
            ///如果区域个数是奇数
            if(flag==1){
                l1 = mid1;
                r2 = mid2;
  
            }else{
                ///如果区域个数是偶数
                l1 = mid1 + 1;
                r2 = mid2;
            }
        }
  
    }
  
    return Math.min(arr1[l1],arr2[l2]);

  }
  module.exports = {
  findMedianinTwoSortedAray : findMedianinTwoSortedAray
  };
  ```