程序员面试金典---18

楸枰～ / 2023-05-03 / 原文

数字流的秩

代码：

var StreamRank = function() {
    this.arr = []
};

/** 
 * @param {number} x
 * @return {void}
 */
StreamRank.prototype.track = function(x) {
    this.arr.push(x)
};

/** 
 * @param {number} x
 * @return {number}
 */
StreamRank.prototype.getRankOfNumber = function(x) {
    let cnt = 0
    for(let item of this.arr){
        if(item <= x){
            cnt++
        }
    }
    return cnt
};

/**
 * Your StreamRank object will be instantiated and called as such:
 * var obj = new StreamRank()
 * obj.track(x)
 * var param_2 = obj.getRankOfNumber(x)
 */

优化：树状数组

function Bit (size) {
    // 定义树状数组
    this.tree = new Array(size + 1).fill(0)
};

Bit.prototype.lowbit = function (x) {
    // 按位与
    return x & -x
}

Bit.prototype.add = function (index, num) {
    while (index && index < this.tree.length) {
        this.tree[index] += num
        index += this.lowbit(index)
    }
}

Bit.prototype.query = function (num) {
    let ans = 0
    while (num) {
        ans += this.tree[num]
        num -= this.lowbit(num)
    }
    return ans
}

var StreamRank = function() {
    this.bit = new Bit(50001)
};

/** 
 * @param {number} x
 * @return {void}
 */
StreamRank.prototype.track = function(x) {
    this.bit.add(x + 1, 1)
};

/** 
 * @param {number} x
 * @return {number}
 */
StreamRank.prototype.getRankOfNumber = function(x) {
    return this.bit.query(x + 1)
};

峰与谷

思路：排序后错位交叉

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function(nums) {
  // 排序
  nums.sort((a, b) => a - b);
  console.log(nums)
  const ans = [...nums];
  let i = 0, left = 0, right = nums.length - 1, flag = 1;
  // 交叉排序
  while (i < nums.length) {
    nums[i++] = ans[flag++ % 2 === 0 ? left++ : right--];
    console.log(nums)
  }
};
/*
nums = [3,5,2,1,6,4]
[ 1, 2, 3, 4, 5, 6 ]
[ 6, 2, 3, 4, 5, 6 ]
[ 6, 1, 3, 4, 5, 6 ]
[ 6, 1, 5, 4, 5, 6 ]
[ 6, 1, 5, 2, 5, 6 ]
[ 6, 1, 5, 2, 4, 6 ]
[ 6, 1, 5, 2, 4, 3 ]
*/