1.題目

1.1第一個題

給定一個范圍在 1 ≤ a[i] ≤ n ( n = 陣列大小 ) 的整型陣列，陣列中的元素一些出現了兩次，另一些只出現一次，

找到所有在 [1, n] 范圍之間沒有出現在陣列中的數字，

您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定回傳的陣列不算在額外空間內，

示例:

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[5,6]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

2.2第二個題

找出陣列中重復的數字，

在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，

示例 1：

輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

限制：

2 <= n <= 100000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

2.解法（自己做的）

兩個題其實想法是差不多的，就放到一起來說了，

2.1 思路

在不開辟新空間的情況下，我們要來達到題目要求，那么我們只能在原陣列上進行操作，那如何在原陣列上操作？而且還需要線性時間，

我們知道陣列元素的范圍一定是1~n 或者 0~ n-1，這樣就優化了排序的時間，普通的陣列排序時間會消耗很多，但這個比較特殊，我們讓每個數回歸到陣列中與其對應的索引上，我們就完成了所謂的排序，如果有不一樣的，那么這個數必定不會和它的索引相對應，這樣我們就找出了消失的陣列，如果交換程序中，目標即該數對應的索引的位置上已經對應了，那么就說明這個數重復了，回傳這個數就可以了，

2.2 代碼

在這里我只用這個解法做了第一個題，

 1 vector<int> findDisappearedNumbers(vector<int>& nums) {
 2         vector<int> v;
 3         for(int i = 0; i < nums.size(); i++) {
 4             while ((nums[i] != i + 1) && (nums[nums[i] - 1] != nums[i])) {
 5                 int t = nums[i];
 6                 nums[i] = nums[t - 1];
 7                 nums[t - 1] = t;
 8             }         
 9         }
10         for(int i = 0; i < nums.size(); i++) {
11             if(nums[i] != i + 1)
12                 v.push_back(i + 1);
13         }
14         return v;
15     }

3.題解

這是官方題解，以下解法來源于這里，

3.1 思路

官方的解法巧妙地利用了求余，也是在原陣列上進行修改，

我們根據求余數求得該數對應的索引，讓該索引的值 +n，回圈完畢后，沒出現的那個數對應的索引的值一定是小于n的，而大于等于2n的就是出現兩次或兩次以上的，

3.2 代碼

這里我只寫了第二個題的解法

 1 int findRepeatNumber(vector<int>& nums) {
 2         int n = nums.size();
 3         for(int i = 0; i < n; i++) {
 4             int x = nums[i] % n;
 5             nums[x] += n;
 6         }
 7         for(int i = 0; i < n; i++) {
 8             if(nums[i] >= 2 * n)
 9                 return i;
10         }
11         return -1;
12     }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259375.html

標籤：其他

上一篇：風炫安全Web安全入門第一期課程總結

下一篇：語法糖

數字中重復數字與消失的數字（兩個題）