題目：一個無序陣列里有99個不重復正整數，范圍從1到100，唯獨缺少一個整數。如何找出這個缺失的整數？
解法一：
創建一個HashMap，以1到100為鍵，值都是0 。然后遍歷整個陣列，每讀到一個整數，就找到HashMap當中對應的鍵，讓其值加一。
由于陣列中缺少一個整數，最終一定有99個鍵值等于1, 剩下一個鍵值等于0。遍歷修改后的HashMap，找到這個值為0的鍵。
假設陣列長度是N，那么該解法的時間復雜度是O（1），空間復雜度是O（N）。
為何時間復雜度是O(1)？兩次遍歷，難道不應該是O(n)嗎？
原文鏈接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653189951&idx=1&sn=0181c95484b67d108672235b14e5ebbb&chksm=8c9905e5bbee8cf3362ccc4c7e091caa18b5783183ce4475b6f011c09c1cb03847ea4cb5220c&scene=21#wechat_redirect
uj5u.com熱心網友回復：
寫錯了吧，都有遍歷了，怎么可能是O(1)uj5u.com熱心網友回復：
筆誤了，是O(N)uj5u.com熱心網友回復：
HashMap 的讀寫也要算進去uj5u.com熱心網友回復：
這個演算法不是最優的吧?正常應該用置位-位檢測的辦法吧.uj5u.com熱心網友回復：
1+2...+100 = 5050如果缺一個，那么把那99個的和-5050就知道了
如果資料項是常數，那么可以看成O（1），雖然它遍歷了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24793.html
標籤：數據結構與算法
上一篇：Kubernetes Logs 如何獲取kube-system pod的日志
下一篇：matlab解決3D曲面問題