旋转数组、只出现一次的数字、两数之和、旋转图像

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

方法一

思路

数据元素向右移动 1 个位置,相当于将数组元素的最后一项截取,然后放到第一项的位置,因此向右移动 k 个位置,就是循环执行上述操作 k 次。而当 k 为数组长度的倍数时,实际相当于没有移动,所以实际需要循环操作的次数为 k % l。

详解

  1. 首先计算出需要循环移动的次数;

  2. 通过数组的 unshift()pop() 方法实现旋转,循环执行 k 次。

unshift() 方法将把它的参数插入数组的头部,并将已经存在的元素顺次地移到较高的下标处,该方法不会创建新数组,而是直接修改原数组。

pop() 方法将删除数组的最后一个元素,把数组长度减 1,并且返回它删除的元素的值。

/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
for (let i = 0; i < k; i++) {
nums.unshift(nums.pop());
}
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    循环遍历的次数取决于k的值,与k值呈线性关系,因此复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    没有申请额外的空间,因此复杂度为 O(1)O(1)

方法二

思路

方法一是将数组中的元素一个一个移动,我们还可以一次性将最后的 k % l 项全部截取,通过扩展运算符‘...’将截取的值放到数组的前边,实现旋转。

详解

  1. 首先还是计算出需要截取的数组元素的长度;

  2. 通过数组的 splice() 方法截取需要移动的元素,然后使用扩展运算符‘...‘将截取的元素当作参数,通过 unshift() 方法将截取的 元素放到数组的前边。

splice() 方法可删除从 index 处开始的零个或多个元素,然后返回被删除的项目。

数组的扩展运算符...相当于将数组展开,主要的使用场景是用于数组复制、合并等。

unshift() 方法的第一个参数将成为数组的 index 为0的新元素,如果还有第二个参数,它将成为 index 为1的新元素,以此类推。

/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
nums.unshift(...nums.splice(l - k, k));
};

复杂度分析:

  • 时间复杂度:O(1)O(1)。 采用一次性截取,所有方法都只执行了 1 次,因此复杂度为 O(1)O(1)

  • 空间复杂度:O(1)O(1)。没有申请额外的空间,因此复杂度为 O(1)O(1)

方法三

思路

先将原数组的所有元素整体往后移动 k 个位置,给需要旋转的元素预留出位置,然后通过替换和删除,实现数组的旋转。

详解

  1. 先将原数组原有的元素从最后一位开始,依次移动到(原下标 + k)的位置;

  2. 然后再从改变后的新数组的下标为 (k - 1) 的元素开始,依次将最后一位赋值给新数组下标为 (k - 1) 的元素,然后删除掉最后一位元素。

/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = function (nums, k) {
const l = nums.length;
k = k % l;
for (let i = l - 1; i >= 0; i--) {
nums[i + k] = nums[i];
}
for (let j = k - 1; j >= 0; j--) {
nums[j] = nums[l + j];
nums.pop();
}
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

    循环遍历的次数取决于数组长度,与数组长度呈线性关系,因此复杂度为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    数组进行了扩充,申请了n个空间,因此复杂度为 O(n)O(n)

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

方法一 分组查询法

思路

将数组遍历,并通过过滤的方法,将值相同的数归集为数组的一个元素,由于除了一个元素,其他元素都会出现两次,所有只要找到过滤的集合的长度为1的那个集合,该集合第一个元素即是该元素。

详解

  1. 遍历数组,由于需要返回值,这里使用map方法

  2. 使用过滤函数,过滤数组中值与当前遍历的元素的值相同的元素

  3. 现在得到了一个存在多个集合的数组,而数组中唯一值的那个元素的集合肯定值存在它自己

  4. 查询这个集合中长度只有1的集合,再取这个集合的第一个元素,即是只出现一次的数字

代码

const singleNumber = (nums) => {
const numsGroup = nums.map(num => nums.filter(v => v === num));
return numsGroup.find(num => num.length === 1)[0];
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    使用了 mapfilter,嵌套遍历,故为O(n2)O(n^2)

  • 空间复杂度:O(n)O(n)

    map方法创建了一个长度为nn的数组,占用了nn大小的空间。

方法二 异或比较法

思路

异或运算符可以将两个数字比较,由于有一个数只出现了一次,其他数皆出现了两次,类似乘法法则无论先后顺序,最后相同的数都会异或成0,唯一出现的数与0异或就会得到其本身,该方法是最优解,直接通过比较的方式即可得到只出现一次的数字。

详解

  1. 将数组的一个元素与下一个元素做异或比较,直接使用reduce方法

  2. 两两异或最后与所有元素都不相同,最后返回的值即是只出现一次的数字。

代码

const singleNumber = (nums) => {
return nums.reduce((accumulator, currentValue) => accumulator ^ currentValue);
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    仅用 reduce 方法遍历,一层遍历,故为O(n)O(n)

  • 空间复杂度:O(1)O(1)

    空间复杂度为常量,占用空间没有随数据量 nn的大小发生改变,故为O(1)O(1)

两数之和

给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一 暴力法

思路

遍历每个元素 x,并查找是否存在一个值与 target - x 相等的目标元素。

详解

  1. 遍历每个元素 x

  2. 并查找是否存在一个值与 target - x 相等的目标元素。

代码

const twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] === target - nums[i]) {
return [i, j];
}
}
}
};

复杂度分析

  • 时间复杂度: O(n2)O( n^2 )

    对于每个元素,通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n2)O( n^2 )的时间。

  • 空间复杂度:O(1)O(1)

    没有申请额为的空间,所以空间复杂度为 O(1)O(1)

方法二 利用 map

思路

将每个元素的值和它的索引加到表中,检查每个元素所对应的目标元素(target - nums[i])是否存在于表中

详解

  1. 将每个元素的值和它的索引添加到表中

  2. 检查每个元素所对应的目标元素(target - nums[i])是否存在于表中

代码

const twoSum = function (nums, target) {
const lookup = {};
let res = [];
nums.some((v, i) => {
if (lookup[target - v] !== undefined) {
res = [lookup[target - v], i];
return true;
} else {
lookup[v] = i;
return false;
}
});
return res;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    我们只遍历了包含有 n 个元素的列表一次,在 map 中进行的每次查找只花费O(1)O(1) 的时间, 因此总的复杂度为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    上述解法中,申请了大小为 nn 的空间,空间复杂度跟数字的个数 n 线性相关,因此为 O(n)O(n)

旋转图像

给定一个 n × n 的二维矩阵表示一个图像,将图像顺时针旋转 90 度。

必须在原地旋转图像,需要直接修改输入的二维矩阵,不要使用另一个矩阵来旋转图像。

示例

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵,使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

方法一 四角旋转

思路

找到一个矩阵中对应点的旋转90度需要涉及到的四个位置的数字,然后将对应的四个数字按照顺时针90度的方法交换即可。

详解

  1. 根据输入得到矩阵的维数;

  2. 以左上角为(0,0)点,从左向右递增,从上向下递增建立矩阵;

  3. 将需要矩阵上需要交换的四个数字存放在一个临时数组中;

  4. 将原本位置上的数据按照数组中的数据进行替换。

代码

function rotate (matrix) {
const n = matrix.length; // n维矩阵
for (let i = 0; i < n; i++) {
for (let j = i; j < n - i - 1; j++) {
const a = [matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j], matrix[n - 1 - j][i]];
matrix[i][j] = a[3];
matrix[j][n - 1 - i] = a[0];
matrix[n - 1 - i][n - 1 - j] = a[1];
matrix[n - 1 - j][i] = a[2];
}
}
}

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    将矩阵进行遍历,二维数组需循环遍历两次,则复杂度为O(n2)O(n^2)

  • 空间复杂度:O(1)O(1)

    所占用空间不会随矩阵的维数而有所变化

方法二 正向对称

思路

先将矩阵沿左上角到右下角的对角线进行对称,然后将矩阵沿垂直中线对称即可。

详解

  1. 根据输入得到矩阵的维数;

  2. 以左上角为(0,0)点,从左向右递增,从上向下递增建立矩阵;

  3. 将矩阵沿左上角到右下角的对角线进行对称,以题目例子 1 为例即:

[
[1,4,7],
[2,5,8],
[3,6,9]
]
  1. 再将矩阵沿垂直中线进行对称。即:

[
[7,4,1],
[8,5,2],
[9,6,3]
]

代码

function rotate (matrix) {
const n = matrix.length;
// 调换对角线元素
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 调换每行的左右元素
for (let k = 0; k < n; k++) {
for (let l = 0; l < Math.floor(n / 2); l++) {
const temp = matrix[k][l];
matrix[k][l] = matrix[k][n - 1 - l];
matrix[k][n - 1 - l] = temp;
}
}
}

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    将矩阵进行遍历,二维数组需循环遍历两次,则复杂度为O(n2)O(n^2)

  • 空间复杂度:O(1)O(1)

    所占用空间不会随矩阵的维数而有所变化

方法三 反向对称

思路

先将矩阵沿右上角到左下角的对角线进行对称,然后将矩阵沿水平中线对称即可。

详解

  1. 根据输入得到矩阵的维数;

  2. 将矩阵沿右上角到左下角的对角线进行对称,以题目例子 1 为例即:

[
[9,6,3],
[8,5,2],
[7,4,1]
]
  1. 将矩阵沿水平中线进行对称。即:

[
[7,4,1],
[8,5,2],
[9,6,3]
]

代码

function rotate (matrix) {
const n = matrix.length;
// 按对角线调换数字
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - 1 - i; j++) {
const temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
matrix[n - 1 - j][n - 1 - i] = temp;
}
}
// 从头到尾交换每一行
for (let k = 0; k < Math.floor(n / 2); k++) {
const temp = matrix[k];
matrix[k] = matrix[n - 1 - k];
matrix[n - 1 - k] = temp;
}
}

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    将矩阵进行遍历,二维数组需循环遍历两次,则复杂度为O(n2)O( n^2)

  • 空间复杂度:O(n)O(n)

    空间与矩阵维数正相关