JavaScript 程序在数组右旋转 K 次后查找第 M 个元素

1. 引言

在日常前端开发中，经常会涉及到对数组进行旋转操作，例如：把[0,1,2,3,4,5,6]右旋转2次，就变成[5,6,0,1,2,3,4]。而在旋转后的数组中查找某个元素也是常见的需求。在本文中，我们将探讨如何使用JavaScript实现数组右旋转K次后查找第M个元素。

2. 数组右旋转K次

2.1 问题分析

假设给定一个数组arr和一个非负整数K，要求将数组右旋转K次。例如，对于数组[0,1,2,3,4,5,6]和K=2，期望输出[5,6,0,1,2,3,4]。我们可以通过以下步骤实现：

将数组最后K个元素取出来，保存为一个新数组

将原数组从后往前依次移动K个位置，腾出前K个位置

将新数组的元素插入到原数组的前K个位置

这里需要注意，当K大于数组长度时，右旋转K次与右旋转K mod length次所得到的结果是相同的。

2.2 代码实现

function rotateArray(arr, k) {
  k = k % arr.length;  // 处理k 大于数组长度的情况
  const temp = arr.splice(arr.length - k);  // 取出最后k个元素
  arr.unshift(...temp); // 将取出的元素插入数组前面
  return arr;
}
const arr = [0, 1, 2, 3, 4, 5, 6];
const k = 2;
console.log(rotateArray(arr, k));  // [5, 6, 0, 1, 2, 3, 4]

3. 数组查找

3.1 问题分析

假设给定一个右旋转后的数组rotatedArr和一个整数M，要求在数组中查找第M个元素。注意，这里的M是数组旋转前的下标。

首先需要将M进行偏移，处理出它在旋转后的数组中的下标。偏移量等于旋转前数组的长度减去旋转次数K再加上M。例如，对于数组[0,1,2,3,4,5,6]，如果K=2，要查找的是下标为2的元素，偏移量就为5。

然后，可以通过二分查找在旋转后的数组中查找第M个元素。具体步骤如下：

判断数组是否为有序数组（左边界小于右边界），如果是，直接使用二分查找

如果不是，找到数组的中间位置mid，将数组分为左右两部分，至少有一部分必然是有序数组

判断M是在有序部分还是无序部分

如果M在有序部分，则在有序部分使用二分查找

如果M在无序部分，则在无序部分递归查找

3.2 代码实现

function findElement(rotatedArr, m) {
  const k = rotatedArr.length;  // 旋转前数组的长度
  const offset = k - rotatedArr.indexOf(rotatedArr[0]);  // M在右旋转数组中的下标偏移量
  const left = 0;
  const right = rotatedArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const rotatedMid = (mid + offset) % k;  // 中间元素在右旋转数组中的下标
    if (rotatedArr[mid] === m) {
      return mid;
    } else if (rotatedArr[mid] > rotatedArr[right]) {  // 左边无序
      if (m >= rotatedArr[left] && m < rotatedArr[mid]) {  // M在左边有序部分
        right = mid - 1;
      } else {  // M在右边无序部分
        left = mid + 1;
      }
    } else {  // 右边无序
      if (m > rotatedArr[mid] && m <= rotatedArr[right]) {  // M在右边有序部分
        left = mid + 1;
      } else {  // M在左边无序部分
        right = mid - 1;
      }
    }
  }
  return -1;  // 没有找到
}
const rotatedArr = [5, 6, 0, 1, 2, 3, 4];
const m = 2;
console.log(findElement(rotatedArr, m));  // 6

4. 整合实现

现在，我们可以将数组右旋转和数组查找的代码组合起来，实现在右旋转数组中查找第M个元素的功能。

function rotateAndFind(arr, k, m) {
  k = k % arr.length;
  const temp = arr.splice(arr.length - k);
  arr.unshift(...temp);
  const rotatedArr = arr;
  const n = rotatedArr.length;
  const offset = n - rotatedArr.indexOf(rotatedArr[0]);
  const left = 0;
  const right = n - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const rotatedMid = (mid + offset) % n;
    if (rotatedArr[rotatedMid] === arr[m]) {
      return rotatedMid;
    } else if (rotatedArr[rotatedMid] > rotatedArr[right]) {  // 左边无序
      if (arr[m] >= rotatedArr[left] && arr[m] < rotatedArr[rotatedMid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {  // 右边无序
      if (arr[m] > rotatedArr[rotatedMid] && arr[m] <= rotatedArr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}
const arr = [0, 1, 2, 3, 4, 5, 6];
const k = 2;
const m = 2;
console.log(rotateAndFind(arr, k, m));  // 6

5. 总结

本文介绍了如何使用JavaScript实现数组右旋转K次后查找第M个元素。在实现右旋转和数组查找的过程中，我们分别使用了splice、unshift、indexOf、二分查找、递归等操作。这些操作对于日常前端开发来说都非常实用。