Java教程

【算法学习日志】一道双指针(误)

本文主要是介绍【算法学习日志】一道双指针(误),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

回归玩家,沉迷了好几天原神了,人事是一点不干天天就知道玩

题目来自力扣寻找两个正序数组的中位数

class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //定义两个布尔指针判断数组1和数组2是否到了尽头,指针p1p2用来遍历
        int p1 = 0,p2 = 0;
        int n1 = nums1.length,n2 = nums2.length;
        //两个数组都未遍历到尽头
        if(p1 < n1 && p2 < n2){
            while(p1 + p2 < (n1 + n2)/2-1) {
                if (p1 == n1 || p2 == n2) {
                    break;
                }
                if (nums1[p1] < nums2[p2]) p1++;
                else p2++;
            }
        }
        //nums1到尽头 nums2没有
        if(p1 >= n1 && p2 < n2){
            while(p1 + p2 < (n1 + n2)/2-1){
                p2++;
            }
        }
        //nums1没到尽头 nums2到了
        if(p1 < n1 && p2 >= n2){
            while(p1 + p2 < (n1 + n2)/2-1){
                p1++;
            }
        }
        //定义left取n/2-1索引处的位置,right取n/2
        double left = 0,right = Double.MAX_VALUE;
        if(p1 < n1 && p2 < n2){
            left = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
            if(p1 == n1 || p2 == n2){
                right = p2 == n2 ? nums1[p1] : nums2[p2];
            }else{
                right = nums1[p1] < nums2[p2] ? nums1[p1] : nums2[p2];
            }
        }else if(p1 >= n1 && p2 < n2){
            left = nums2[p2];
            if(p2 < n2-1)  right = nums2[p2+1];
        }else if(p1 < n1 && p2 >= n2){
            left = nums1[p1];
            if(p1 < n1-1) right = nums1[p1+1];
        }

        double mid = 0;
        if((n1+n2) % 2 == 1){
            //如果n数字太小导致取不到right
            if(right == Double.MAX_VALUE) mid =left;
            else mid = right;
        }else{
            mid = (left+right)/2;
        }
        return mid;
    }
}

时间复杂度是O(m+n)

如果用类似归并的想法去做的话应该能到O(log(m+n))这样

不管了等会再看吧!还差20抽保底!稻妻一堆任务没做!今天一定要把雷神肝出来!

这篇关于【算法学习日志】一道双指针(误)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!