# 概念
# 一. 数据结构
# 类别
- 线性表：数组，队列，链表，栈、散列表等
- 非线性表：二叉树、堆、图、跳表、Trie数等
# 区别
- 并非简单的前后关系
- 连续的内存空间和相同类型的数据。线性表适合随机访问但是删除插入的时候为了保证连续性，就要做大量的数据搬移工作
# 二. 算法
（思维导图待续）
# 基础方法
- 递归
- 排序
- 二分查找
- 搜索
- 哈希算法
- 贪心算法
- 分治算法
- 回溯算法
- 动态规划
- 字符串匹配
# 算法特性
- 输入: 算法具有0个或多个输入
- 输出: 算法至少有1个或多个输出
- 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性：算法中的每一步都有确定的含义，不会出现二义性
- 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
# 三. 复杂度
# 时间复杂度
时间复杂度简而言之就是执行的次数
T(n) = O(f(n))
大O时间复杂度表示法，渐进时间复杂度，表示执行时间与数据
- T(n) : 代码执行的时间
- n：数据规模的大小
- f（n）：每行代码执行的次数总和
- O: 代码的执行时间T(n)与表达式f(n)成正比
方法：
- 关注循环执行次数最多的一段代码
忽略公式中的常量低阶，系数
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
忽略公式中的常量低阶，系数
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
忽略公式中的常量低阶，系数
类别： **
- 多项式量级：
常量阶：O(1)
不存在循环递归
对数阶 ：O(logn) 线性阶：O(n) 线性对数阶：O(nlogn)
归并排序，快速排序
平方阶：O(n2)... O(nk) O(m+n)，O(m*n)
- 非多项式量级：
指数阶：O(2的n次方) 阶乘阶：O(n!)、
# 空间复杂度
空间复杂的即占用内存的大小
# 基础思考题
# 1. 两数之和（#1）
给定一个整数数组 nums 和一个目标值 target， 请你在该数组中找出和为目标值的那 两个 整数， 并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。 但是， 你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
2
3
4
5
6
7
8
9
10
解法： 暴力for循环，重点不能重复元素，通过i!=j将重复元素去掉
var twoSum = function(nums, target) {
const len = nums.length
for (let i = 0; i < len - 1; i++) {
for (let j = 1; j < len; j++) {
if (nums[i] + nums[j] === target && i != j) {
return [i, j]
}
}
}
};
2
3
4
5
6
7
8
9
10
180 ms 34. 8 MB
# 2. 三数之和（#15）
给定一个包含 n 个整数的数组 nums， 判断 nums 中是否存在三个元素 a， b， c， 使得 a + b + c = 0？ 找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
2
3
4
5
6
7
8
9
10
11
解法：
var threeSum = function(nums) {
// 最左侧值为定值，右侧所有值进行两边推进计算
let res = [];
nums.sort((a, b) => a - b);
let size = nums.length;
if (nums[0] <= 0 && nums[size - 1] >= 0) {
// 保证有正数负数
let i = 0;
while (i < size - 2) {
if (nums[i] > 0) break; // 最左侧大于0，无解
let first = i + 1;
let last = size - 1;
while (first < last) {
if (nums[i] * nums[last] > 0) break; // 三数同符号，无解
let sum = nums[i] + nums[first] + nums[last];
if (sum === 0) {
res.push([nums[i], nums[first], nums[last]]);
}
if (sum <= 0) {
// 负数过小，first右移
while (nums[first] === nums[++first]) {} // 重复值跳过
} else {
while (nums[last] === nums[--last]) {} // 重复值跳过
}
}
while (nums[i] === nums[++i]) {}
}
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
204 ms 47. 4 MB J
# 3. 多数元素（#169）
给定一个大小为 n 的数组， 找到其中的多数元素。 多数元素是指在数组中出现次数大于⌊ n / 2⌋ 的元素。
你可以假设数组是非空的， 并且给定的数组总是存在多数元素。
示例 1:
输入: [3, 2, 3]
输出: 3
示例 2:
输入: [2, 2, 1, 1, 1, 2, 2]
输出: 2
2
3
4
5
6
7
8
9
10
11
12
解法一： 进行排序，取中间数则为众数
var majorityElement = function(nums) {
if (nums.lenghth == 1) return nums[0]
nums.sort();
return nums[parseInt(nums.length / 2)];
};
2
3
4
5
100 ms 37. 8 MB
解法二： 投票法：相同计数器加1，不相同计数器减1，最终剩下的数为众数
var majorityElement = function(nums) {
let count = 0;
let candidate = null;
nums.forEach(function(num) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
});
return candidate;
};
2
3
4
5
6
7
8
9
10
11
12
13
76 ms 37. 7 MB
# 4. 缺失的第一个正数（#41）
给定一个未排序的整数数组， 找出其中没有出现的最小的正整数。
示例 1:
输入: [1, 2, 0]
输出: 3
示例 2:
输入: [3, 4, -1, 1]
输出: 2
示例 3:
输入: [7, 8, 9, 11, 12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)， 并且只能使用常数级别的空间。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
解法一： 通过排序，从0开始循环，如果两数之间相减大于1则两数之间的第一个数值就是那个缺失的正数
var firstMissingPositive = function(nums) {
nums = nums.filter(item => item > 0)
let len = nums.length
if (len) {
nums.sort((a, b) => a - b)
if (nums[0] != 1) {
return 1
} else {
for (let i = 0; i < len - 1; i++) {
if (nums[i + 1] - nums[i] > 1) {
return nums[i] + 1
}
}
return nums[len - 1] + 1
}
} else {
return 1
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
80 ms 35 MB
解法二： 暴力法，拿到数组的长度加2，不断地判断数字是不是在里面
var firstMissingPositive = function(nums) {
for (var i = 1; i < nums.length + 2; i++) {
if (nums.indexOf(i) < 0) return i
}
};
2
3
4
5
72 ms 34. 2 MB
https://www.cnblogs.com/qiuxirufeng/p/11525322.html https://blog.csdn.net/qq_31196849/article/details/78529724
# 排序概览
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) |
| 希尔排序 | O(nlogn) | O(nlog2(n)) | O(nlog2(n)) | O(1) |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) |
# 排序讲解
# 1. 冒泡排序
冒泡排序重复地走访过要排序的数列，一次比较两个元素，将大的数据放在后面。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成，大的数据慢慢移到尾部。
# 算法描述
- 比较相邻元素，如果第一个比第二个大就交换两个顺序
- 对每对相邻元素重复同样工作
# 动图
# 代码
function bubbleSort(arr) {
let len = arr.length
for (let i = len - 1; i > 0; i--) {
for (let j = 0; j < i; j++) { // j<i
let temp = arr[j]
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
2
3
4
5
6
7
8
9
10
11
12
13
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {}
}
2
3
# 2. 选择排序
# 算法描述
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
# 动图
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧
# 代码
（待续）
# 3. 插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
# 算法描述
- 第一个元素默认为已排序
- 取出下个元素，在已排序的元素序列中从后往前扫描，
- 如果已排序的数比该数大则往后挪，直到对比到比它小的排序树，插入改排序数到后面
# 动图
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧
- 稳定
- 基本有序
- 规模小
# 4. 希尔排序（待续）
希尔排序（缩小增量排序）也是一种插入排序，但它会有限比较距离较远的元素，将整个待排序的记录序列分割成为若干子序列分别进行插入。非稳定
# 算法描述
- 选择一个增量序列，t1，t2... . . tk，其中ti>tj，tk=1
- 按照增量序列个数k，对序列进行k趟排序
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 怎么界定分组，一般是二分之一或者三分之一
# 动图
# 5. 归并排序
归并排序的核心是分治法。将一个数组切成两半，递归切到单个元素，然后重新组装合并。单个元素合并成小数组，小数组合并成大数组，直至排序完成，二路归并。像1024
# 算法描述
- 将长度为n的的输入序列分成两个长度为n/2的子序列
- 子序列再递归切到单个元素
- 单个元素重新组装合并成小数组，小数组合并成大数组，直至排序完成
# 动图
# 6. 快速排序
分治法, 它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。
# 算法描述
- 将长度为n的的输入序列分成两个长度为n/2的子序列
- 子序列再递归切到单个元素
- 单个元素重新组装合并成小数组，小数组合并成大数组，直至排序完成
# 动图
快速排序的时间复杂度和归并排序一样，O(n log n)，但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，比如排一个有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，选取基准值 9 ，那么需要切分 n - 1 次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了 O(n)，当然极端情况出现的概率也是比较低的。 所以说，快速排序的时间复杂度是 O(nlogn)，极端情况下会退化成 O(n)，为了避免极端情况的发生，选取基准值应该做到随机选取，或者是打乱一下数组再选取。 另外，快速排序的空间复杂度为 O(1)。
# 排序思考题
# 1. 什么是稳定排序，什么是原地排序
是否稳定
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
# 2. 排序数组（#912）
给定一个整数数组 nums， 将该数组升序排列。
示例 1：
输入：[5, 2, 3, 1]
输出：[1, 2, 3, 5]
示例 2：
输入：[5, 1, 1, 2, 0, 0]
输出：[0, 0, 1, 1, 2, 5]
提示：
1 <= A.length <= 10000 -
50000 <= A[i] <= 50000
2
3
4
5
6
7
8
9
10
11
12
13
14
15
解法：
var sortArray = function(nums) {
nums.sort((a, b) => a - b)
return nums
};
2
3
4
# 3. 数组中的第K个最大元素(#215)
在未排序的数组中找到第 k 个最大的元素。 请注意， 你需要找的是数组排序后的第 k 个最大的元素， 而不是第 k 个不同的元素。
示例 1:
输入: [3, 2, 1, 5, 6, 4] 和 k = 2
输出: 5
示例 2:
输入: [3, 2, 3, 1, 2, 4, 5, 5, 6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的， 且 1≤ k≤ 数组的长度。
2
3
4
5
6
7
8
9
10
11
12
13
解法：
var findKthLargest = function(nums, k) {
nums.sort((a, b) => a - b)
return nums[nums.length - k]
};
2
3
4
80 ms 35. 9 MB
# 4. 最大间距(#164)
给定一个无序的数组， 找出数组在排序之后， 相邻元素之间最大的差值。
如果数组元素个数小于 2， 则返回 0。
示例 1:
输入: [3, 6, 9, 1]
输出: 3
解释: 排序后的数组是[1, 3, 6, 9], 其中相邻元素(3, 6) 和(6, 9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2， 因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数， 且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
解法：
var maximumGap = function(nums) {
let len = nums.length
if (len < 2) return 0
let max = 0
let space
for (let i = len - 1; i > 0; i--) {
let temp
for (let j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
}
}
if (i < len - 1) {
space = nums[i + 1] - nums[i]
if (space > max) {
max = space
}
}
}
return Math.max(max, nums[1] - nums[0])
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
80 ms 35. 9 MB
https://www.cnblogs.com/onepixel/p/7674659.html https://www.jianshu.com/p/edfa25a2b1ca https://github.com/wangzheng0822/algo/blob/master/javascript/12_sorts/QuickSort.js https://github.com/DangoSky/algorithm/tree/master/Algorithm-notes