arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个 块 ( 子数组 ),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。 请问 我们最多能将数组分成多少块?

区块链毕设网qklbishe.com为您提供问题的解答

arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个子数组),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。请问我们最多能将数组分成多少块?

我提个不太好的解法:
关键:上一块的最大值必须要小于下一块的最小值;
使用TreeMap(红黑树,按照值大小排序)记录数组所有值及其个数;
利用max记录当前块的最大值,每次经过一个元素,更新max,并将map中这个key降低一个。
若通过这次降低使得这块的最大值小于剩下元素的最小值,就可以将这块划分出去
    public int maxChunksToSorted (int[] nums) {         TreeMap<Integer, Integer> map = new TreeMap<>();         for (int n : nums) {             map.put(n, map.getOrDefault(n, 0) + 1);         }         int n = nums.length, cnt = 1, max = nums[0];         for (int i = 0; i < n; i++) {             int t = map.get(nums[i]) - 1;             max = Math.max(max, nums[i]);             if (t == 0) {                 map.remove(nums[i]);             } else {                 map.put(nums[i], map.get(nums[i]) - 1);             }              if (!map.isEmpty()) {                 int key = map.firstKey();                 if (key >= max) {                     //当前值都小于后面的所有值,可以分割一段。                     max = Integer.MIN_VALUE;                     cnt++;                 }             }         }         return cnt;     }  

23:50

以上就是关于问题arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个 块 ( 子数组 ),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。 请问 我们最多能将数组分成多少块?的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。

区块链NFT链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个 块 ( 子数组 ),并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排序后的原数组相同。 请问 我们最多能将数组分成多少块?

发表评论