写点什么

分割数组

作者:掘金安东尼
  • 2022-10-24
    美国
  • 本文字数:1015 字

    阅读完需:约 3 分钟

题目

给定一个数组 nums ,将其划分为两个连续子数组 left 和 right, 使得:


left 中的每个元素都小于或等于 right 中的每个元素。left 和 right 都是非空的。left 的长度要尽可能小。在完成这样的分组后返回 left 的 长度 。


用例可以保证存在这样的划分方法。


示例 1:
输入:nums = [5,0,3,8,6]输出:3解释:left = [5,0,3],right = [8,6]
示例 2:
输入:nums = [1,1,1,0,6,12]输出:4解释:left = [1,1,1,0],right = [6,12]
提示:
2 <= nums.length <= 1050 <= nums[i] <= 106可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。
复制代码

题解

拿到题首先想到是朴素的做法,就是每个点依次向左右扩展,如果发现左边的最大值一直小于右边的最小值,那么该点就是答案。但是该方法时间复杂度是 O(n* n),看一下数据量应该不能过。


那就想到通过离散化排序,我们把数组的下标保存,然后排序,从左往右再遍历下如果排序的最大值和下标相同,说明从左往右能组成连续的且排序小于右半部分的数组。该方法的时间复杂度是 O(n*logn);


双指针的办法也是一开始就想到的,优先缩减右半部分,但是发现会缩过头。后来也是加上数组保存前缀最大值和后缀最小值,然后往后去修正。看了题解才感觉有点 low,哈哈哈。


/** * @param {number[]} nums * @return {number} */var partitionDisjoint = function(nums) {//离散化+排序    let arr = nums.map((val,index)=>({val,index}));    arr.sort((a,b)=>a.val-b.val);    let i = 0,max=-1;    for(;i<arr.length;i++){        max =Math.max(max,arr[i].index);        if(max === i) break;    }    return max+1;}var partitionDisjoint = function(nums) {//双指针    let left = 0,right = nums.length-1;    let leftMax = [nums[0]],rightMin = [];    rightMin[right] = nums[right];    while(left<right){        if(leftMax[left]<=rightMin[right]){            right--;            rightMin[right] = Math.min(rightMin[right+1],nums[right]);        }else{            left++;            leftMax[left] = Math.max(leftMax[left-1],nums[left]);        }    }    //console.log(left,right,leftMax,rightMin);    while(leftMax[left]>rightMin[++right]){        left++;        leftMax[left] = Math.max(leftMax[left-1],nums[left]);    }    return left+1;};
复制代码


发布于: 刚刚阅读数: 3
用户头像

安东尼陪你度过漫长编程岁月~ 2022-07-14 加入

真正的大师,永远怀着一颗学徒的心(易)

评论

发布
暂无评论
分割数组_算法_掘金安东尼_InfoQ写作社区