Lt384. 打乱数组

384. 打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

​

示例：
输入 [“Solution”, “shuffle”, “reset”, “shuffle”] [[[1, 2, 3]], [], [], []] 输出 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]] 解释 Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2] solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3] solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]
​

提示：

• 1 <= nums.length <= 200
• -106 <= nums[i] <= 106
• nums 中的所有元素都是 唯一的
• 最多可以调用 5 * 104 次 reset 和 shuffle

思路

先对比左右两个是否颜色不一致，不一致的话直接返回数组长度-1。如果一致，可以推断出，最长的距离一定是中间某个颜色不同的点到左端或者右端的距离的一个，找到最左边和最右边最近的不同的颜色的点。返回：最左端到离最右端最近不同颜色的点的距离（r）和最右端到最左端最近不同颜色点距离（colors.length - 1 - l），两者中大的那一边。

解答

/**
 * @param {number[]} colors
 * @return {number}
 */
const maxDistance = function (colors) {
  let l = 0;
  let r = colors.length - 1;
  const leftColor = colors[l];
  if (colors[l] !== colors[r]) return colors.length - 1;
  while (leftColor === colors[l]) l++;
  while (leftColor === colors[r]) r--;
  return Math.max(colors.length - 1 - l, r);
};