1.算法題目
給定一個整數(shù)數(shù)組结啼，判斷是否存在重復(fù)元素劈猿。
如果任何值在數(shù)組中出現(xiàn)至少兩次入热，函數(shù)返回 true。如果數(shù)組中每個元素都不相同解总，則返回 false贮匕。
示例 1:
輸入: [1,2,3,1]
輸出: true
示例 2:
輸入: [1,2,3,4]
輸出: false
示例 3:
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true
2.算法思路
算法思路：
- 暴力法：冒泡法思想，逐一檢查每個元素在數(shù)組中是否存在重復(fù)元素花枫，遇到重復(fù)元素則返回 true刻盐，否則繼續(xù)遍歷，算法復(fù)雜度較高O(n^2)劳翰；
- 排序查找算法：考慮到有序數(shù)組查找重復(fù)元素只需要遍歷一次敦锌，所以可以通過高效的排序算法將數(shù)組元素排序，然后遍歷一遍數(shù)組即可確定數(shù)組是否存在重復(fù)元素佳簸，算法復(fù)雜度是 O(nlogn + n)乙墙，即 O(nlogn)；
- 哈希表：
3.算法代碼
算法代碼：
- 根據(jù)算法思路1編寫的代碼比較簡單生均，但在leecode上面提交代碼會提示超時听想，而且代碼實現(xiàn)邏輯比較簡單就不提供了；
- 借助排序算法編寫的算法代碼如下：
public static boolean containsDuplicate(int[] nums) {
Arrays.sort(nums); // 對數(shù)組排序
for (int i = 0; i < nums.length - 1; i ++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
- 根據(jù)哈希表思路編寫的算法代碼如下：
Set<Integer> set = new HashSet<>(nums.length);
for (int i = 0; i < nums.length; i ++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
}
return false;
注意：對于一些特定的 n 不太大的測試樣例马胧，哈希表實現(xiàn)方法的運行速度可能會比排序查找算法更慢汉买。這是因為哈希表在維護(hù)其屬性時有一些開銷。要注意佩脊，程序的實際運行表現(xiàn)和 Big-O 符號表示可能有所不同蛙粘。Big-O 只是告訴我們在 充分 大的輸入下垫卤，算法的相對快慢。因此出牧，在 n 不夠大的情況下穴肘， O(n) 的算法也可以比 O(nlogn) 的更慢。
??如果你有疑問或更好的算法思路崔列，歡迎留言交流Ｉ液帧！赵讯！
??如果感覺我的文章對您有所幫助盈咳，麻煩動動小手給個喜歡，謝謝１咭怼Ｓ阆臁！
