一、題目大意
給定一個包含 n + 1 個整數的陣列 nums ，其數字都在 [1, n] 范圍內（包括 1 和 n），可知至少存在一個重復的整數，
假設 nums 只有 一個重復的整數 ，回傳 這個重復的數 ，
你設計的解決方案必須 不修改 陣列 nums 且只用常量級 O(1) 的額外空間，
示例 1：
輸入：nums = [1,3,4,2,2]
輸出：2
示例 2：
輸入：nums = [3,1,3,4,2]
輸出：3
提示：
- 1 <= n <= 105
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一個整數 出現 兩次或多次 ，其余整數均只出現 一次
進階：
-
如何證明 nums 中至少存在一個重復的數字?
-
你可以設計一個線性級時間復雜度 O(n) 的解決方案嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/find-the-duplicate-number
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
這道題給我們n+1個數，所有的數都在[1, n]區域內，首先讓證明必定會有一個重復數，題目要求不能改變原陣列，即不能給原陣列排序，又不能用多余空間，那么hash的就不用考慮了，又要求時間小于O(n^2)，只能考慮用二分搜索法了，在區間[1, n]中搜索，首先求出中點mid，然后遍歷整個陣列，統計所有小于等于mid的數的個數，如果個數小于等于mid，則說明重復值在[mid+1, n]之間，反之，重復值在[1, mid-1]之間，然后依次類推，直到搜索完成，此時的low就是我們要求的重復值，
三、解題方法
3.1 Java實作
public class Solution {
public int findDuplicate(int[] nums) {
int left = 1;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int num : nums) {
cnt += (num <= mid) ? 1 : 0;
}
if (cnt <= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
四、總結小記
- 2022/10/25 旦行好事，莫問前程
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/519303.html
標籤：其他
上一篇：全球名校AI課程庫（26）| MIT麻省理工 · 計算機科學的數學基礎課程『Mathematics for Computer Science』
下一篇：EFCore不保存關系表上的更改