162. 寻找峰值

方法1 「二分查找」

var findPeakElement = function(nums) {
  let l = 0, r = nums.length - 1, mid = (r - l >> 1) + l;
  while (r > l) {
    if (nums[mid] > nums[mid + 1]) r = mid; // 下坡
    else l = mid + 1; // 上坡
    mid = (r - l >> 1) + l;
  }
  return mid;
};

描述

将 nums 比作是一座山，山的两头，是谷底，并且山是没有水平路段的。一个人从某一个点「mid」向左侧「mid + 1」爬山

• 若这一段路是上坡，那么在区间 [mid + 1, R] 之间，必然存在峰值点，令 L = mid + 1，细分区间；（当前点 mid 不可能是峰值点，因为下一个点比它大）
• 若这一段路是下坡，那么在区间 [L, mid] 之间，必然存在峰值点，令 R = mid，细分区间；（当前点 mid 有可能是峰值点，因为它可能还会比前一个点大）
• 循环上述步骤，直到循环结束，L = R = mid，此时就找到了峰值点；

核心：如果是上坡，就往前走；如果是下坡，就不动。

题目中说，假设 nums[-1] = nums[n] = -∞，也就是说我们可以将两侧比作是谷底；

提示中说，对于所有有效的 i 都有 nums[i] != nums[i + 1]，也即是说我们可以认为山是没有水平路段的，要么上坡，要么下坡；

方法2 「暴力循环」

var findPeakElement = function(nums) {
  const len = nums.length;
  // 处理特殊情况
  if (len === 1 || nums[0] > nums[1]) return 0; // 左侧边界处理 或 仅一个成员
  if (nums[len - 1] > nums[len - 2]) return len - 1; // 右侧边界处理
  for (let i = 1; i < len - 1; i++) {
    if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
  }
};

描述

由于题目描述中说了，左右两侧是负无穷「谷底」，所以会有以下几种特殊情况。

• 只有一个成员的情况，nums.length === 1，该成员就是峰值点；
• 端点成员是峰值点；

去掉上述的特殊情况后，后续的逻辑就很简单了，从第 2 个成员开始遍历到倒数第 2 个成员，若当前成员大于左右两侧的成员，那么该成员就是峰值点，将其返回即可。

类似题目

169. 多数元素

方法1 「排序」

 var majorityElement = function(nums) {
  return nums.sort((a, b) => a - b)[Math.floor(nums.length / 2)];
};

注解

多数元素，也就是众数。由于众数的个数是过半的，也就是说，若 nums 是有序的，则中间点的元素必然就是多数元素。

结果分析

方法2 「hash-table」

var majorityElement = function(nums) {
  const len = nums.length, half = len / 2, m = new Map();
  for (let i = 0; i < nums.length; i++) {
    const item = nums[i];
    m.set(item, (m.get(item) || 0) + 1);
    if (m.get(item) > half) return item;
  }
};

注解

使用 hash-table 来解，思路很简单，就是遍历 nums，把每一次遍历到的值丢到 hash-table 中，一旦某个值，在 hash-table 中出现的次数大于 「n / 2」 次，那么将该数返回即可。

可以先生成 hash-table，再遍历 hash-table 寻找众数。

也可以在初始化 hash-table 的同时，进行判断。「上述代码使用的就是这种方式」

结果分析

方法3 「分治」

var majorityElement = function (nums) {
  // 统计数组 nums 的区间 [start, end] 中，num 出现的次数。
  const countInRange = (start, end, num) => {
    let count = 0;
    for (let i = start; i <= end; i++) {
      if (nums[i] === num) count++;
    }
    return count;
  };
  // 获取数组 nums 的区间 [start, end] 中的众数。
  const majorityElementRec = (start, end) => {
    // 若区间 [start, end] 中，只有一个数字，那么该数就是众数。
    if (start === end) return nums[start];
    // 细分区间，找众数
    let mid = start + Math.floor((end - start) / 2);
    const l_majority = majorityElementRec(start, mid); // 左侧子区间的众数
    const r_majority = majorityElementRec(mid + 1, end); // 右侧子区间的众数
    // 在合并之前，判断的两个子组件的众数是否相同，若相同，则不用合并，直接返回众数即可。
    if (l_majority === r_majority) return l_majority;
    // 合并区间，找众数
    const l_count = countInRange(start, end, l_majority);
    const r_count = countInRange(start, end, r_majority);
    return l_count > r_count ? l_majority : r_majority;
  };
  return majorityElementRec(0, nums.length - 1);
};

注解

核心：先求得最终子问题的解，再不断将解合并，得到原问题的解。

• 最终的子问题：一个区间中只有一个数，求该区间中的众数。结果很明显，该区间的这个数就是我们要找的众数。

• 将最终的子问题向上合并：一个区间中有两个数，求该区间的众数。在上一步，我们求得了子问题的解。若这两个子问题的解是相同的，那么合并后的区间的众数也就是子问题的解。若它们的解是不同的，则继续向上合并。

// 下面结合示例1 [3, 2, 3] 来简单介绍一下流程
1. [3, 2, 3] -> 细分区间 -> [3, 2] 和 [3]，发现左区间还可以细分
2. [3, 2] -> 细分区间 -> [3] 和 [2]
// 细分区间结束，现在开始求子问题的解，并在必要的时候合并区间。
3. 得到解：[3] -> 3，[2] -> 2

如果两个区间中的众数相同，那么直接返回该众数。否则，将两区间合并，在合并后的区间中计算出这两个众数出现的次数，将出现次数多的返回。

特殊情况：若两个子区间中的众数在合并后的区间中出现次数依旧相同，则随便返回一个，继续合并即可（此时必然还没有合并到头）。因为如果合并后的区间为 [0, nums.length - 1]，那么是不可能会有这种情况出现的。

189. 旋转数组

1. 暴力解法

var rotate = function(nums, k) {
  while (k) {
    nums.unshift(nums.pop())
    k--
  }
};

。。。不给过。。。还不知道错哪。。。

2. 暴力解法

var rotate = function (nums, k) {
  const len = nums.length;
  k %= len;
  let last_num = nums[len - 1]; // 最后一个成员
  while (k) {
    for (let i = len - 1; i > 0; i--) {
      nums[i] = nums[i - 1]
    }
    nums[0] = last_num;
    last_num = nums[len - 1];
    k--;
  }
};

依旧不给过。。。还不知道错哪。。。

3. 暴力解法

var rotate = function (nums, k) {
  k %= nums.length;
  const reverse = nums.reverse(); // [7, 6, 5, 4, 3, 2, 1]
  const splice_part1 = reverse.splice(0, k).reverse(); // [5, 6, 7]
  const splice_part2 = reverse.reverse(); // [1, 2, 3, 4]
  const newArr = [...splice_part1, ...splice_part2]; // [5, 6, 7, 1, 2, 3, 4]
  for (let i = 0; i < newArr.length; i++) {
    nums[i] = newArr[i]
  }
};

解题思路：

• 整体反转
• 切片
• 对切片再进行反转
• 拼接

4. 暴力解法

var rotate = function (nums, k) {
  const newArr = [],
    len = nums.length;
  k %= len;
  for (let i = len - k; i < len; i++) {
    newArr.push(nums[i])
  }
  // newArr => [5, 6, 7]
  for (let i = 0; i < len - k; i++) {
    newArr.push(nums[i]);
  }
  // newArr => [5, 6, 7, 1, 2, 3, 4]
  // nums = newArr
  for (let i = 0; i < len; i++) {
    nums[i] = newArr[i]
  }
};

解题思路：

• 切片
• 先把后半部分装入原数组
• 再把前半部分装入原数组

5. 双指针

// 反转数组(left_index ~ right_index)
/* 示例： 
输入：[1, 2, 3, 4] 1, 3
输出：[1, 4, 3, 2]
注解：将数组 [1, 2, 3, 4] 索引 1 到 3 的部分进行反转
 */
const reverseArr = (arr, left_index, right_index) => {
  while (left_index <= right_index) {
    let temp = arr[left_index]
    arr[left_index] = arr[right_index]
    arr[right_index] = temp
    left_index++
    right_index--
  }
  return arr;
}
var rotate = function (nums, k) {
  const len = nums.length;
  k %= len;
  reverseArr(nums, 0, len - 1) // 整体反转
  reverseArr(nums, 0, k - 1) // 前半部分反转
  reverseArr(nums, k, len - 1) // 后半部分反转
};

勉勉强强算是双指针吧。。。就是封装了一个 reverseArr 函数，实现原理和 3、4 都差不多。