問題：
寫一個函式：
class Solution { public int solution(int[] A) {...} }即，給定一個包含
AN 個整數的陣列，回傳在 中不出現的最小正整數（大于 0）A。例如：
給定
A = [1, 3, 6, 4, 1, 2]，函式應該回傳5。
給定A = [1, 2, 3]，函式應該回傳4。
給定A = [?1, ?3]，函式應該回傳1。假使，假設：
N是范圍內的整數[1..100,000]；陣列的每個元素A都是范圍內的整數[?1,000,000..1,000,000]。復雜：
預期的最壞情況時間復雜度為
O(N); 預期的最壞情況空間復雜度為O(N)（不計算輸入引數所需的存盤空間）。
我可以知道為什么我回答這個問題的分數這么低嗎？我的解決方案如下：
public static int solution(int[] A) {
int returnInt = 1;
int maxInt = 0;
if (A.length == 0)
return returnInt;
for (int i = 0; i < A.length; i )
{
if (A[i] > maxInt)
maxInt = A[i];
}
if (maxInt < returnInt)
return returnInt;
return maxInt % 2 == 0
? maxInt - 1
: maxInt 1;
}
該解決方案只有一個 for 回圈，我不明白為什么我的分數很低。
uj5u.com熱心網友回復：
您可以使用;HashSet<int> exists存盤所有正面專案 A然后你可以檢查號碼1..exists.Count是否在exists.
C#代碼：
public static int solution(int[] A) {
if (A is null || A.Length <= 0)
return 1;
var exists = new HashSet<int>();
foreach (int item in A)
if (item > 0)
exists.Add(item);
for (int i = 1; i <= exists.Count; i)
if (!exists.Contains(i))
return i;
return exists.Count 1;
}
在最壞的情況下，我們有
時間復雜度： O(n)，假設我們有良好的散列函式：foreach回圈是O(n)- 添加到散列集 is ，O(1)也是for (int i = 1; i <= exists.Count; i)-O(n)在散列集的情況下ContainsO(1)
空間復雜度：（ O(n)哈希集）
如果我們可以讓自己的時間復雜度稍微差一點——O(n * log(n))我們只能有O(1)空間復雜度：
C#代碼：
public static int solution(int[] A) {
if (A is null || A.Length <= 0)
return 1;
Array.Sort(A);
for (int i = 0, prior = 0; i < A.Length; prior = Math.Clamp(A[i ], 0, A.Length))
if (A[i] > 0 && A[i] != prior 1)
return prior 1;
return Math.Clamp(A[A.Length - 1] 1, 1, A.Length);
}
uj5u.com熱心網友回復：
OP 的性能“低”當然是因為它產生了錯誤的答案。
return maxInt % 2 == 0 ? maxInt - 1 : maxInt 1;沒有什么意義。
簡化演算法。
給定一個包含 N 個整數的陣列 A，回傳 A 中未出現的最小正整數（大于 0）。
認識到在值 [1...N 1] 之間，必須至少有 1 個值不在A[]. A[]最多有N不同的值。鴿巢原理
花費 O(N) 時間，O(N) 更多空間解決方案，沒有哈希表，沒有 BST：
形成一個 T/F 值的陣列 B[N 1] - 將所有設定為 false。索引此陣列 [1...N 1]。花費 O(N) 時間，O(N) 更多空間。
遍歷陣列 A。對于每個 A[i]，測驗 A[i] <= N（并且 A[i] >= 1）。如果 A[i] 在范圍內，則設定 B[A[i]] = true。花費 O(N) 時間。
遍歷陣列B。找到第一個為假的B[i]，就是
i答案。花費 O(N) 時間。
示例 C 代碼：
size_t LowestMissingPositive(size_t N, const int A[N]) {
unsigned char Used[N 1];
memset(Used, 0, sizeof Used);
for (size_t i = 0; i < N; i ) {
if (A[i] >= 1 && (unsigned) A[i] <= N) {
Used[A[i] - 1] = 1;
}
}
for (size_t i = 0; i <= N; i ) {
if (!Used[i]) {
return i 1;
}
}
// Code never expected to get here.
return N 1;
}
A[]注意：“陣列 A 的每個元素都是 [?1,000,000..1,000,000] 范圍內的整數”，除了需要處理該范圍的型別之外，這并不是一個重要的規定。例如，至少 21 位寬的整數型別。
uj5u.com熱心網友回復：
創建一個包含所有大于 0 的
L整數的串列。AO(n)排序
L。O(n lg(n))如果
L為空，則回傳 1。如果L[0]不是 1，則回傳 1。遍歷
L. 如果L[i] != i，則回傳 i。O(n)
總復雜度 = O(n n lg(n)) = O(n lg(n)).
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505885.html
標籤：算法