【JavaScript】LeetCode：86-90

86 只出现一次的数字

• 异或
• x ^ x = 0，x ^ 0 = x，相同为0，相异为1，且满足交换律。
• 例如：[4, 1, 2, 1, 2] => 1 ^ 1 ^ 2 ^ 2 ^ 4 = 0 ^ 0 ^ 4 = 0 ^ 4 = 4，最后的结果即为重复一次的数字。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res = 0;
    for(let item of nums){
        res ^= item;
    }
    return res;  
};

87 颜色分类

• 双指针
• i 指向0的下一个位置，j 指向1的下一个位置。
• k 遍历数组，① 若该位置为0，则将当前数与 i 指向的数进行交换，i 和 j 指针都向后移动一位；② 若该位置为1，则将当前数与 j 指向的数进行交换，j 指针向后移动一位。
• 注意：情况①时，若 i < j，则说明 i 指向的数为1，做交换时会把1换到后面去（即k指向的数），应该将当前数与 j 指向的数进行交换，把1换回去。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let i = 0, j = 0;
    for(let k = 0; k <= nums.length; k++){
        if(nums[k] == 0){
            [nums[i], nums[k]] = [nums[k], nums[i]];
            if(i < j){
                [nums[j], nums[k]] = [nums[k], nums[j]];
            }
            i++;
            j++;
        }else if(nums[k] == 1){
            [nums[j], nums[k]] = [nums[k], nums[j]];
            j++;
        }
    }
};

88 下一个排列

• 例子：数组nums = [1, 2, 3, 5, 4]。
• 从后往前遍历数组，查找第一个升序的数对，记为 i 和 j 。
  i = 3，j = 5。
• 从后往前遍历数组，查找第一个 > nums[i]的数，记为tmp。
  tmp = 4。
• 交换nums[i]和nums[tmp]。
  nums = [1, 2, 4, 5, 3]。
• 将 i 后面的元素按升序进行排序，得到结果。
  nums = [1, 2, 4, 3, 5]。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    let len = nums.length;
    let i = len - 2, j = len - 1;
    while(i >= 0){
        if(nums[i] < nums[j]){
            break;
        }
        i--, j--;
    }
    let tmp = -1;
    for(let k = len - 1; k > i; k--){
        if(nums[k] > nums[i]){
            tmp = k;
            break;
        }
    }
    [nums[tmp], nums[i]] = [nums[i], nums[tmp]];
    let right = nums.slice(j, len);
    right.sort((a, b) => a - b);
    let n = 0, m = i + 1;
    while(m < len){
        nums[m] = right[n];
        m++, n++;
    }
};

89 寻找重复数

• 快慢指针找环形链表的入口。
• 创建一个链表，节点为[0, 1, …, n]，nums索引值 i 的next为nums[i]。
• 若存在重复元素s，链表中一定会同时有两条边指向节点x，节点x即为环的入口。
• 例如：nums = [1, 3, 4, 2, 2]，链表为：0 => 1，1 => 3，2 => 4，3 => 2，4 => 2，这里可以发现，2为环形链表的入口，即为重复元素。

var next = function(nums, index){
    return nums[index];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = 0, fast = 0;
    while((slow == 0 && fast == 0) || slow != fast){
        fast = next(nums, next(nums, fast));
        slow = next(nums, slow);
    }
    slow = 0;
    while(slow != fast){
        slow = next(nums, slow);
        fast = next(nums, fast);
    }
    return slow;
};

90 前K个高频元素

• 最小堆

  节点	索引值
  当前节点	i
  父节点	(i - 1) / 2向下取整
  左孩子	2 * i + 1
  右孩子	2 * i + 2
  最后一个非叶子节点	(length - 2) / 2向下取整

• 自上往下：与左右孩子进行比较，若均 > 左右孩子，则与左右孩子中较小值交换，否则与 < 自身的孩子交换。

• 自下往上：与父节点进行比较，若 > 父节点，则与父节点交换。

• push()：插入末尾，然后自下而上判断一次。

• pop()：取出堆顶元素，将堆中最后一个元素与堆顶元素交换，然后自上往下判断一次。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class Heap {
    constructor(comparator = (a, b) => a - b, data = []){
        this.data = data;
        this.comparator = comparator;
        this.heapify();
    }

    heapify(){
        if(this.size() < 2) return;
        for(let i = Math.floor(this.size() / 2) - 1; i >= 0; i--){
            this.bubbleDown(i);
        }
    }

    peek(){
        if(this.size() === 0) return null;
        return this.data[0];
    }

    insert(value){
        this.data.push(value);
        this.bubbleUp(this.size() - 1);
    }

    pop(){
        if(this.size() == 0){
            return null;
        }
        const result = this.data[0];
        const last = this.data.pop();
        if(this.size() != 0){
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return result;
    }

    bubbleUp(index){
        while(index > 0){
            const parentIndex = Math.floor((index - 1) / 2);
            if(this.comparator(this.data[index], this.data[parentIndex]) < 0){
                this.swap(index, parentIndex);
                index = parentIndex;
            }else{
                break;
            }
        }
    }

    bubbleDown(index){
        const lastIndex = this.size() - 1;
        while(true){
            const leftIndex = index * 2 + 1;
            const rightIndex = index * 2 + 2;
            let findIndex = index;
            if (leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0){
                findIndex = leftIndex;
            }
            if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0){
                findIndex = rightIndex;
            }
            if(index != findIndex){
                this.swap(index, findIndex);
                index = findIndex;
            }else{
                break;
            }
        }
    }

    swap(index1, index2){
        [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
    }

    size(){
        return this.data.length;
    }
}

var topKFrequent = function(nums, k) {
    const map = new Map();
    for(const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }

    const priorityQueue = new Heap((a, b) => a[1] - b[1]);

    for(const items of map.entries()){
        priorityQueue.insert(items);
        if(priorityQueue.size() > k){
            priorityQueue.pop();
        }
    }

    const res = [];
    for(let i = priorityQueue.size() - 1; i >= 0; i--){
        res[i] = priorityQueue.pop()[0];
    }

    return res;
};