【LeetCode】数据结构与算法入门-第一天（一）
近日无大事，闲来看看数据结构写写题，活跃一下脑力思维。
在计算机科学中，数据结构是计算机中存储、组织数据的方式。数据结构与算法比较抽象，学习起来还是需要一定的毅力。广义上讲数据结构就是指一组数据的存储结构，算法就是操作数据的一组方法。
算法和数据结构是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。
* 题目来自：LeetCode 数据结构入门
217. 存在重复元素
较为特别的一些测试用例：
- [1, 2, 3, 1]
- [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
- [1, 2, 3, 4]
- [0]
- [7, 3, 2, 1, 2]
- [1, 5, -2, -4, 0]
- [2, 14, 18, 22, 22]
目前个人所想可分为三种不同实现的方向：
- 方向一：不使用数组所提供的便利性 API
- 除基础操作外（push、pop、unshift、shift、slice、splice）
- 方向二：可以使用数组所提供的所有 API
- 方向三：其他技巧
* 注意：以下出现的代码可以使用 for 改写
01 - 方向一
1. 双循环法
1.1 暴力
function containsDuplicate(nums: number[]): boolean {
let i = 0
let j = 0
while (i < nums.length) { // n
const item = nums[i]
while (j < nums.length) { // n
if (item === nums[j]) {return true}
j++
}
i++
}
return false
};特点：所有元素都参与对比判断包括自己
时间复杂度：O(n^2)
问题：自己与自己比会直接为 true
结果：不适用
1.2 优化
function containsDuplicate(nums: number[]): boolean {
let i = 0
let j = i + 1
while (i < nums.length) { // n
const item = nums[i]
while (j < nums.length) { // n - 1
if (item === nums[j]) { return true }
j++
}
i++
j = i + 1
}
return false
};特点：每次循环都仅和自身以及历史之外的元素比较
时间复杂度：On(n * (n - 1)) => O(n^2)
问题：因为是顺序，如果重复的元素位于较末尾则会耗费太多时间进行无效对比
结果：可实现，但耗时较多
2. 双指针
2.1 使用空间
function containsDuplicate(nums: number[]): boolean {
const arr = []
const findNum = (num: number): boolean => {
let kl = 0
let kr = arr.length - 1
while (kl <= kr) {
if (num === arr[kl] || num === arr[kr]) { return true }
kl++
kr--
}
return false
}
let i = 0
let j = nums.length - 1
while (i <= j) { // n / 2
const l = nums[i]
const r = nums[j]
if (i === j && findNum(l)) { return true } // n / 2 + 1
if (l === r) { return true }
if (findNum(l)) { return true } // n / 2 + 1
if (findNum(r)) { return true } // n / 2 + 1
arr.push(l)
arr.push(r)
i++
j--
}
return false
};特点：外层只循环 n / 2 次，但需要额外空间来进行记录历史数据，本质上还是双循环
时间复杂度：O(3m * n) => O(mn)
问题：需要额外空间记录已遍历过的值，且需要再从历史中遍历一次，需要处理多种情况的边界条件
结果：可实现，但实现逻辑上可优化，可不用额外空间实现
2.2 优化，不使用空间
function containsDuplicate(nums: number[]): boolean {
let i = 0
let j = nums.length - 1
while (i <= j) { // n
const l = nums[i]
const r = nums[j]
if (l === r && i !== j) return true
let ci = i + 1
let cj = j - 1
while (ci <= cj) { // n
if (l === nums[ci] || l === nums[cj]) return true
if (r === nums[ci] || r === nums[cj]) return true
ci++
cj--
}
i++
j--
}
return false
};特点：内外都使用了双指针，但其本质上还是双循环，但是边界条件大大减少了
时间复杂度：O(n * n) => O(n^2)
问题：虽然不再占用额外空间且内循环也使用了双指针，但并未改变其复杂度
结果：可实现，未改变其复杂度
02 - 方向二
1. 利用 indexOf
function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i++) { // n
if (nums.indexOf(nums[i], i + 1) !== -1) return true // n
}
return false
};特点：简单、直观、易懂
时间复杂度：O(n * n) => O(n^2)
问题：虽然使用了indexOf API 实现，看似 O(1) 但是其内部还是 O(n)
结果：可实现
2. 利用 sort
function containsDuplicate(nums: number[]): boolean {
if (!nums || !nums.length) return false
nums = nums.sort()
for (let i = 0; i < nums.length; i++) {
if (nums[i] === nums[i + 1]) return true
}
return false
};特点：排序后相同元素会相邻，每次将当前与下一个元素进行对比即可
时间复杂度：O(n + n) => O(n)
问题：单一类型元素可行，如出现复杂类型则需要考虑更多情况处理
结果：可实现
03 - 方向三
1. 利用对象 key
function containsDuplicate(nums: number[]): boolean {
if (!nums || !nums.length) return false
const obj: { [key: string]: number } = {}
for (let i = 0; i < nums.length; i++) {
if (obj[nums[i]]) { return true }
if (!obj[nums[i]]) { obj[nums[i]] = 1 }
}
return false
};特点：利用对象的 key 不可重复特性，如遇到已有的 key 则可确认是存在重复元素
时间复杂度：O(n)
问题：属于利用数据类型特性，并非算法实现
结果：可实现
2. 利用 Set 新数据类型
function containsDuplicate(nums: number[]): boolean {
if (!nums || !nums.length) return false
const nNums = new Set(nums)
return nums.length > nNums.size
};特点：利用 Set 天然去重特性，通过数组长度对比可以直接得出结论
时间复杂度：O(1)
问题：属于利用数据类型特性，并非算法实现
结果：可实现
3. 利用 Map 新数据类型
function containsDuplicate(nums: number[]): boolean {
if (!nums || !nums.length) return false
const nNums = new Map()
for (let i = 0; i < nums.length; i++) {
if (nNums.has(nums[i])) { return true }
else { nNums.set(nums[i], 1) }
}
return false
};特点：利用 Map 数据结构特性，其原理与 object 类似
时间复杂度：O(n)
问题：属于利用数据类型特性，并非算法实现
结果：可实现
最后
按题意给出标签：数组、哈希表、排序。以上实现方式中只有 二、2，三、1，三、2，三、3 是可符合题意，且是较优实现。
学习是反人性的，对大多数人来说是相对痛苦的。学成之后的愉悦感、成就感是无可比拟的。但是这个过程艰难而枯燥。
题目来源：
LeetCode 数据结构入门： https://leetcode-cn.com/study-plan/data-structures
版权声明：
本文版权属于作者 林林林小帅，未经授权不得转载及二次修改。
转载或合作请在后台留言及联系方式。
腾讯云开发者
