2366. Minimum Replacements to Sort the Array


题目

——将数组排序的最少替换次数

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

  • For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return the minimum number of operations to make an array that is sorted in non-decreasing order.

Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0. 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

思路

题目大意是说,给定数组nums,每次操作可以将任意数字拆分成和等于原数字的两个数字,求最小拆分次数,使得拆分后的数组不降序。

拿到题先看数据规模,nums量级105,nums[i]量级109,大概率是动规贪心了。

我们来看看有没有可复用的子问题。

首先我们知道,再不计次数的前提下,任意数组都可以拆成非降序。(可以拆成全数字1)e.g.[3,2,1] => [(1,1,1),(1,1),(1)]

其次,数组里任意一个数字,是否需要拆分,取决于它的后面是否有比它大的数字。

对于数组最后一个数字,最优策略是不拆分,因为如果拆分,可能导致其他数字需要拆分,这增加了全局的拆分次数。对于数组的倒数第二个数字,即nums[-2],如果nums[-2]<=nums[-1],满足非降序要求,反之则需要拆分。那么,如果需要拆分,应该拆几次&拆成多少呢?

我们知道,拆分某个数字,仍需要保证拆分后的数字是非降序的,同时,拆分后的第一个数字应该尽可能的大(这样才能让nums[0:-2]尽可能的不切分)。

举个例子,nums=[2,5,2],对于5,我们有一下几种拆分方式。

不拆->[5]

拆1次->[2,3]

拆2次->[1,2,2]

拆3次->[1,1,1,2]

拆4次->[1,1,1,1,1]

观察可得,拆分次数越多,拆分后第一个数字就越小;同时,给定拆分次数的情况下,如果想让拆分后的第一个数字最大,最优策略是尽可能平均拆分。

拆分次数可以二分,也可以直接求。

待拆分数字n,将n拆成不降序的m份(n1,n2,…,nm),且ni<T,同时n1最小

拆分次数m = ceil(n / T),拆分后最小元素n1=n // m

一通分析下来,我们发现这道题不仅有可重入的子问题,子问题的最优解就是全局最优解——我们得到了一个贪心解法。

代码

import math
class Solution(object):
    def minimumReplacement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        ret = 0
        cur_n = nums[-1]
        for n in reversed(nums):
            if n <= cur_n:
                cur_n = n
                continue
            pieces = int(math.ceil(1.0 * n / cur_n))
            
            ret += pieces - 1
            cur_n = n // pieces
                
                
        return ret

AC,收工!



——此处是内容的分割线——

除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.utopiafar.com/2022/08/09/leetcode-2366-minimum-replacements-to-sort-the-array/

码字不易,如果觉得内容有帮助,欢迎留言or点赞!


发表回复

您的电子邮箱地址不会被公开。