Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/06 22:59)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串261/719 (看更多)

1539. Kth Missing Positive Number 給你一個已經排序且嚴格遞增的整數陣列和一個數字k，返回第k個丟失的整數，這個整數範圍為1~N，且不包含陣列已經有的數字。 Example: Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9. 法一暴力思路： 1.遍歷陣列，如果陣列裡面沒有小於k的數，直接返回k 2.如果陣列裡面有小於k的數字，k遞增 3.返回k Java Code： --------------------------------------------------- class Solution { public int findKthPositive(int[] arr, int k) { for (int n : arr) { if (n <= k) { k++; } } return k; } } --------------------------------------------------- 法二二分搜尋思路： 1.因為陣列嚴格遞增，透過a[i]的值我們其實可以獲得一些資訊，考慮下表： a[0]=2 缺1 a[1]=3 缺1 a[2]=4 缺1 a[3]=7 缺3 [1,5,6] 我們觀察到陣列第i個位置缺少的元素數量會是 a[i] - i - 1 2.所以我們只要找到一個數字使缺失的元素數量大於等於k，我們就可以得知第k個丟失的數字了，因為陣列已經排序，所以可以把k當作二分搜尋的pivot 3.同方法一的思路，我們只要得到滿足條件的k，把k加上小於k的數字數量(l)就可以獲得第k的丟失的數字 Java Code： ------------------------------------- class Solution { public int findKthPositive(int[] arr, int k) { int l = 0, r = arr.length - 1; while (l <= r) { int mid = (l + r)/2; if (arr[mid] - mid - 1 < k) { l = mid + 1; } else { r = mid-1; } } return l + k; } } ------------------------------------- -- https://i.imgur.com/3e5CZfj.jpg