排序算法题
学到的解题方法
双指针
设置map，值设为键
理解题意的根本条件
冒泡排序(bubbleSort)
const bubbleSort = function(Array) {
if(!Array.length || Array.length === 1) return Array
for(let i = 0;i < Array.length;i++ ) {
let flag = true
for(let j = 0;j < Array.length-i-1;j++) {
if(Array[j] > Array[j+1]) {
flag = false // 如果存在某一轮没有轮换过，代表已经全部是递增了
const temp = Array[j]
Array[j] = Array[j+1]
Array[j+1] = temp
}
}
if(flag) break
}
return Array
}
let a = [2,35,4,4,6,8,4,1,5,6,31,56,-1]
console.log(bubbleSort(a));选择排序(insertionSort)
注意，选择排序是 不稳定 的排序算法，交换的过程中打乱了原有的相对顺序
// i把Array分为左边有序列，右边无序列
// 每轮从无序列中找出最小的 与 有序列最右侧i处 交换
// 与冒泡排序不同之处在于每轮交换次数只有一次
const selectionSort = function(Array) {
if(!Array.length || Array.length === 1) return Array
const len = Array.length
for(let i = 0; i < len-1; i++) { // 注意这里不该是i<len,能省一点是一点
let min = i
for(let j = i+1; j < len; j++) { // 注意这里不该是j = i,能省一点是一点
if(Array[min] > Array[j]) { min = j }
}
const temp = Array[i]
Array[i] = Array[min]
Array[min] = temp
}
return Array
}
let a = [2,35,4,4,6,8,4,1,5,6,31,56,-1]
console.log(selectionSort(a));插入排序(insertionSort)
// i把Array分为左边有序列，右边无序列
// 每轮把i依次从右往左对比，与比自己大的数交换 (XXX,错误思路)
// 保存i 每轮把i依次从右往左对比，比自己大的数，就右移，最后j+1放i
const insertionSort = (arr) => {
if (arr.length <= 1) return
// (0,i) 代表有序区间 i代表无序区间这轮即将要插入有序区间的数
for (let i = 1; i < arr.length; i++) {
const temp = arr[i]
let j = i - 1
// j 属于 [0,i-1],从后向前比较,比temp大的就后移
for (j; j >= 0; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j]
} else {
break
}
}
// 直到 找到第一个<j或=j的数下标 或循环完j=-1,
// temp放这个数后面(j+1)
arr[j + 1] = temp
}
return arr
}
let a = [2,35,4,4,6,8,4,1,5,6,31,56,-1]
console.log(insertionSort(a));合并两个有序数组(LeetCode 88)
var merge = function(nums1, m, nums2, n) {
m--
n--
for(let i = nums1.length -1 ;n>=0; i --) { // 只要nums2全部排进1了就结束了
nums1[i] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]
}
return nums1
};颜色分类(LeetCode 75)
// 只要原地排序就行，这里试一下插入排序
var sortColors = function(nums) {
if(nums.length <= 1) return nums
for(let i = 1; i < nums.length; i++) {
const temp = nums[i]
let j = i // 这里的插入排序不小心用了j = i,不是很符合逻辑，报了多次错才做出来
for(j; j > 0; j--) { // 应该用 j = i - 1,其他地方对应修改
if(nums[j-1] > temp) {
nums[j] = nums[j-1]
} else {
break
}
}
nums[j] = temp
}
};部分排序(leetcode16)
标准做法是：找两个数，m n，[m,n]区间内是乱序需要排序的数组
m是满足 其右侧 存在 小于自己的数(表示此数以右边未递增，需要排序) 的数
m右侧最小数记为min，往左遇到 比min小的就替换min(不需要更新边界m)，遇到比min大的 就是 更新m
n是满足 其左侧 存在 大于自己的数(表示此数以左未递增，需要排序) 的数
n左侧最大数记为max，往右遇到 比max大的就替换max(不需要更新边界n)，遇到比max小的 就是 更新n
无注释版
var subSort = function(array) {
if(!array.length || array.length === 1) return [-1,-1]
const last = array.length - 1
let m = last
let n = 0
let max = - Number.MAX_VALUE
let min = Number.MAX_VALUE
for(let i = 0; i <= last; i++) {
if(array[i] < max) n = i
else max = array[i]
if(array[last - i] > min) m = last - i
else min = array[last - i]
}
return n === 0 ? [-1,-1] : [m,n]
};// 注意到成为 左边界m 的条件是，
// 1.所有自己左侧的数 必须开始递减
// 2.所有自己左侧的数 必须小于 右侧最小的数min
var subSort = function(array) {
if(!array.length || array.length === 1) return [-1,-1]
const last = array.length - 1
let m = last // 左边界m 初始指向最右边
let n = 0 // 右边界n 初始指向最左边
let max = - Number.MAX_VALUE // 初始为JS最小值
let min = Number.MAX_VALUE // 初始为JS最大值
for(let i = 0; i <= last; i++) {
// 从左往右找 右边界n，n右边的数必须大于n左边的数max
if(array[i] < max) { // 如果发现小于max的，就更新右边界n
n = i
} else { // 如果正常，n右边的数 大于max，则不用更新n，且max更新
max = array[i]
}
// 同时从右往左找 左边界m，注意 因为是从右往左，并且复用for循环，所以是last-i
if(array[last - i] > min) {
m = last - i
} else {
min = array[last - i]
}
}
// n边界没有动表示 从左到右，找不到一个数小于前一个数，即本就是递增
return n === 0 ? [-1,-1] : [m,n]
};我的解法
// 我是从左往右一个个判断这个数是不是当前最小的数，找到左边界，右边界同理。
var subSort = function(array) {
let start = -1,end = -1;
for(let i = 0; i < array.length; i++) {
let flag = false
for(let j = i + 1; j < array.length; j++) {
if(array[i] > array[j]) {
start = i
flag = true
break
}
}
if(flag) break
}
for(let i = array.length - 1; i > start; i--) {
let flag = false
for(let j = i - 1; j > start; j--) {
if(array[i] < array[j]) {
end = i
flag = true
break
}
}
if(flag) break
}
return [start,end]
};计算右侧小于当前元素的个数(LeetCode 315)
合并 K 个升序链表(LeetCode 23)
没啥好说的，最简单的，一个个合并
var mergeKLists = function(lists) {
let result = null
for(let i = 0; i < lists.length; i++) {
result = mergeTwoLists(result,lists[i])
}
return result
};
var mergeTwoLists = function(l,r) {
let pl = l,pr = r, result = new ListNode(),pResult = result
while(pl && pr) {
if(pl.val > pr.val) {
pResult.next = pr
pr = pr.next
} else {
pResult.next = pl
pl = pl.next
}
pResult = pResult.next
}
pResult.next = pl ? pl : pr
return result.next
}有序数组的平方(LeetCode 977)
双指针
var sortedSquares = function(nums) {
let i = 0, j = nums.length - 1,result = []
while(i <= j) {
if(nums[i]*nums[i] < nums[j]*nums[j]) {
result.unshift(nums[j]*nums[j])
j--
} else {
result.unshift(nums[i]*nums[i])
i++
}
}
return result
};我的解法
var sortedSquares = function(nums) {
let stack = [],result = []
for(let i = 0; i < nums.length; i++) {
const temp = Math.pow(nums[i],2)
if(nums[i] < 0) { // 小于0的就压入栈
stack.push(temp)
} else {
while(stack.length && stack[stack.length-1] <= temp) {
result.push(stack.pop()) // 大于0的数压入栈之前先验证stack里有没有符合的
}
result.push(temp)
}
}
while(stack.length) {
result.push(stack.pop())
}
return result
};两数之和(LeetCode 11)
设置map，值设为键
var twoSum = function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++) {
if(map.get(nums[i]) !== undefined) { // 注意这里的get 和下面的 set需要相反,注意这里要写!== undefined,因为可能是0
return [i,map.get(nums[i])]
} else {
map.set(target - nums[i],i) // 将值设置为键
}
}
return []
};
