題1

描述

給定整數(shù)數(shù)組 A，每次 move 操作將會(huì)選擇任意 A[i]，并將其遞增 1。
返回使 A 中的每個(gè)值都是唯一的最少操作次數(shù)。
示例 1:
輸入：[1,2,2]
輸出：1
解釋：經(jīng)過一次 move 操作，數(shù)組將變?yōu)?[1, 2, 3]。
示例 2:
輸入：[3,2,1,2,1,7]
輸出：6
解釋：經(jīng)過 6 次 move 操作，數(shù)組將變?yōu)?[3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能讓數(shù)組的每個(gè)值唯一的。
提示：
0 <= A.length <= 40000
0 <= A[i] < 40000

題解1 排序法

思路：先用Arrays.sort()對(duì)數(shù)組進(jìn)行排序，遍歷排序后的數(shù)組，如果后一個(gè)元素小于前一個(gè)元素，則后一個(gè)元素+1，移動(dòng)的步數(shù)等于當(dāng)前位置變更后的值與數(shù)組原先值之差，所有差之和即為總的移動(dòng)步數(shù)。

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

題解2 計(jì)數(shù)法

思路：我拿到題目后的第一種思路是計(jì)數(shù)＋暴力法，在小數(shù)據(jù)的測(cè)試用例下都可以得到正確答案，思路也沒有問題，疑惑的是無法通過超級(jí)大且多的數(shù)據(jù)。后來看了官方的解答知道了答案。

雖然 A[i] 的范圍為 [0, 40000)，但我們有可能會(huì)將數(shù)據(jù)遞增到 40000 的兩倍 80000。這是因?yàn)樵谧顗那闆r下，數(shù)組 A 中有 40000 個(gè) 40000，這樣要使得數(shù)組值唯一，需要將其遞增為 [40000, 40001, …, 79999]，因此用來統(tǒng)計(jì)的數(shù)組需要開到 80000。

當(dāng)我們找到一個(gè)沒有出現(xiàn)過的數(shù)的時(shí)候，將之前某個(gè)重復(fù)出現(xiàn)的數(shù)增加成這個(gè)沒有出現(xiàn)過的數(shù)。注意，這里 「之前某個(gè)重復(fù)出現(xiàn)的數(shù)」 是可以任意選擇的，它并不會(huì)影響最終的答案，因?yàn)閷?P 增加到 X 并且將 Q 增加到 Y，與將 P 增加到 Y 并且將 Q 增加到 X 都需要進(jìn)行 (X + Y) - (P + Q) 次操作。例如當(dāng)數(shù)組 A 為 [1, 1, 1, 1, 3, 5] 時(shí)，我們發(fā)現(xiàn)有 3 個(gè)重復(fù)的 1，且沒有出現(xiàn)過 2，4 和 6，因此一共需要進(jìn)行 (2 + 4 + 6) - (1 + 1 + 1) = 9 次操作。

class Solution {public int minIncrementForUnique(int[] A) {int[] count = new int[80000];for (int x: A) count[x]++;int ans = 0, taken = 0;for (int x = 0; x < 80000; ++x) {if (count[x] >= 2) {taken += count[x] - 1;ans -= x * (count[x] - 1);}else if (taken > 0 && count[x] == 0) {taken--;ans += x;}}return ans;} }

題2

描述

給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。
注意這五個(gè)元素可為任意順序。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
說明:
為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請(qǐng)注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對(duì)實(shí)參作任何拷貝
int len = removeElement(nums, val);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中 該長(zhǎng)度范圍內(nèi) 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

題解

思路：類似于昨天的題2，用i指針來移動(dòng)，用j指針來指向與val相同的元素位置，用i指針指向的元素向前覆蓋j位置的值

class Solution {public int removeElement(int[] nums, int val) {// 使用雙指針if (nums == null || nums.length == 0)return 0;int j = 0;for(int i = 0; i < nums.length; i++){if(nums[i] != val){nums[j] = nums[i];j++;}}return j;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】3月22日打卡-Day7的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。