【演算法-初級-陣列】存在重復元素（JavaScript實作）
博客說明
文章所涉及的部分資料來自互聯網整理，當然還有自己個人的總結和看法，分享的目的在于共建社區和鞏固自己，參考的資料如有侵權，請聯系本人洗掉！幸好我在，感謝你來！
演算法說明
語言只是實作演算法的一種手段，思路才是最為重要的，
如果有多種解法的話，只選一種語言作為解答對比，
如果單獨將某一種演算法的話，會以多種語言實作，對比語言的特性，
😎因為多對多的話，篇幅會拉的比較大，影響觀看體驗！
題目
題目地址
217. 存在重復元素
題目說明
給定一個整數陣列，判斷是否存在重復元素，
如果存在一值在陣列中出現至少兩次，函式回傳 true ，如果陣列中每個元素都不相同，則回傳 false ，
示例 1
輸入: [1,2,3,1]
輸出: tru
示例 2
輸入: [1,2,3,4]
輸出: false
示例 3
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true
思路
暴力解法
怎么能缺少暴力解法呢，這畢竟是大腦最直白的想法，當然保留！😁
直接遍歷，拿一個輔助陣列，一個一個往里面塞，直到遇到相等的，那么就是它！
這里就不貼代碼了（暴力的解法畢竟不美觀哈！），看一下結果！
但注意哈！不可恥！畢竟通過了?，
排序
思路
在暴力解法的時候遇到了一個問題，就是時間和空間復雜度都比較高，
因為在輔助陣列里面也需要遍歷，因為原陣列的不是按照順序來的，所以需要我們來一場排序，會解決掉一些問題，
因為重復的元素都會在相鄰的位置，只需要當前的元素左右扭頭看一下即可，
JavaScript
之前是用的js寫的暴力，所以對比js的排序改進版，
看下面的圖，發現然而并沒卵用，該高還是得高，時間有那么一點改進，
😶因為排序也是需要開銷的，
再來！
代碼
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
if (nums.length < 1) return false
// 排序
nums.sort((a, b) => a - b)
const n = nums.length;
for (var i = 0; i < n - 1; i++) {
if (nums[i] === nums[i + 1]){
return true
}
}
return false
};
復雜度分析
時間復雜度
O(NlogN)，其中 N 為陣列的長度，
需要對陣列進行排序，
空間復雜度
O(logN)，其中 N 為陣列的長度，
哈希表
思路
看我們暴力解法的時候，有兩個比較麻煩的點，一個是不確定重復的元素的出現的位置（所以上一步來了排序），一個是需要輔助的陣列來記錄，
這次就利用哈希表來存盤已遍歷的元素，再次插入相同的元素的時候哈希表就能給出反應，只需要遍歷就行！
JavaScript
代碼
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
if (nums.length < 1) return false
// 哈希表
const set = new Set();
const n = nums.length;
for (var i = 0; i < n; i++) {
if (set.has(nums[i])) {
return true
}else {
set.add(nums[i])
}
}
return false
};
復雜度分析
時間復雜度
O(N)，其中 N 為陣列的長度，
空間復雜度
O(N)，其中 N 為陣列的長度，
感謝
萬能的網路
放在LeetCode上的題解
以及勤勞的自己，個人博客，GitHub測驗，GitHub
公眾號【歸子莫】，小程式【小歸博客】
如果你感覺對你有幫助的話，不妨給我點贊👍吧，持續關注也行哈！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/393954.html
標籤：其他
上一篇：關于vue專案的注意.初級版