leetcode945-使数组唯一的最小增量

原题

给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1

返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:

输入: [1,2,2] 输出: 1
解释: 经过一次 move 操作,数组将变为 [1, 2, 3]。

示例 2:

输入: [3,2,1,2,1,7] 输出: 6
解释: 经过 6 次 move 操作,数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示:

  1. 0 <= A.length <= 40000
  2. 0 <= A[i] < 40000

解法

思想

先排序,然后保证每个数字都大于前面的数字。

代码

class Solution {
    public int minIncrementForUnique(int[] A) {
        if(A.length == 0) return 0;
        Arrays.sort(A);
        int sum = 0;
        int last = A[0];
        for(int i = 1; i<A.length;i++){
            if(A[i]<=last){
                sum += last+1-A[i];
                last = last+1;
            }else{
                last = A[i];
            }
        }
        return sum;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode945-%e4%bd%bf%e6%95%b0%e7%bb%84%e5%94%af%e4%b8%80%e7%9a%84%e6%9c%80%e5%b0%8f%e5%a2%9e%e9%87%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月21日 22:24
下一篇 2020年3月22日 10:40

相关推荐

  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04620
  • 剑指offer59-队列的最大值

    原题(来源Leetcode) 请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度…

    算法 2020年3月7日
    0130
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    080
  • leetcode744-寻找比目标字母大的最小字母

    原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子,如果目标字母tar…

    算法 2020年1月5日
    0220
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    080
  • leetcode21-合并两个有序链表

    原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入: 1->2->4, 1->3->4 输出: 1->1->2->3-…

    2019年12月17日
    0100
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    090
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode152-乘积最大子数组

    原题 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出:…

    算法 2020年5月18日
    0130

发表回复

登录后才能评论