两个数组的交集、一周中的第几天、有效的数独、除资深以外数组的乘积和存在重复元素

两个数组的交集

给定两个数组,计算数组交集。

  1. 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。

  2. 我们可以不考虑输出结果的顺序。

示例

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

方法一 模拟哈希

思路

遍历第一个数组,将第一个数组的值、该值出现的次数,以(key:value)的形式存储下来,接着遍历第二个数组,判断是否在(key:value)中存在,存在则 value 减去 1,继续。

详解

  1. 定义模拟哈希的对象 hashObject、定义 result 数组存放最终符合条件的结果;

  2. for 循环遍历第一个数组,将数组中每个值作为 key、出现次数作为 value 存到 hashObject 对象中,第一次出现 value 为 1,再次出现 value 加 1;

  3. for 循环遍历第二个数组,判断第二个数组中每个值是否在 hashObject 中存在,即在 hashObject 作为 key 对应的 value 为 1 或者大于 1,如果存在将该值 push 到 result 数组中,并将该值对应的 value 减去 1;

  4. 返回 result 即可;

代码

const intersect = function (nums1, nums2) {
const hashObject = {};
for (let i = 0; i < nums1.length; i++) {
if (hashObject[nums1[i]]) {
hashObject[nums1[i]] += 1;
} else {
hashObject[nums1[i]] = 1;
}
}
const result = [];
for (let j = 0; j < nums2.length; j++) {
if (hashObject[nums2[j]]) {
result.push(nums2[j]);
hashObject[nums2[j]] -= 1;
}
}
return result;
};

复杂度分析

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

    分别 for 循环遍历两个数组,每个耗费时间都是 O(n)O(n),总的时间复杂度O(n) O(n)

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

    定义了一个 hashObject 对象存储第一个数组每个值、每个值出现的次数,空间大小最大为 O(n)O(n)、定义一个 result 数组存放最终符合条件的结果,空间大小最大为O(n)O(n),两者一起空间大小最大为 2n2n,所以空间复杂度为O(n)O(n)

方法二 长短数组

思路

找出两个数组中的长短数组,遍历短数组,判断值是否存在于长数组中,如果存在,记录并且删除长数组中的该值,继续。

详解

  1. 定一个 longerArr 存放两个数组中较长的数组、shorterArr 存放两个数组中较短的数组,定义 result 数组存放最终结果;

  2. for 循环遍历 shorterArr 数组,如果 shorterArr 数组中当前元素在 longerArr 数组中存在,就将该值 push 到 result 数组中,并且在 longerArr 数组中删除对应当前值的元素;

  3. 返回 result 数组即可;

const intersect = function (nums1, nums2) {
const longerArr = nums1.length > nums2.length ? nums1 : nums2;
const shorterArr = nums1.length > nums2.length ? nums2 : nums1;
const result = [];
for (let i = 0; i < shorterArr.length; i++) {
if (longerArr.indexOf(shorterArr[i]) > -1) {
result.push(shorterArr[i]);
longerArr.splice(longerArr.indexOf(shorterArr[i]), 1);
}
}
return result;
};

复杂度分析:

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

    只对长度较小的数组进行一次 for 循环遍历,时间复杂度为 O(n)O(n)

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

    需要额外的空间分别存储长短数组,该表最多需要存储 2n2n 个元素,故空间复杂度为 O(n)O(n)

一周中的第几天

给你一个日期,请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数:day、month 和 year,分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

说明:给出的日期一定是在 19712100 年之间的有效日期。

示例 1:

输入:day = 31, month = 8, year = 2019
输出:"Saturday"

示例 2:

输入:day = 18, month = 7, year = 1999
输出:"Sunday"

示例 3:

输入:day = 15, month = 8, year = 1993
输出:"Sunday"

方法一 直接求解法

思路

说明中指出了:给出的日期一定是在 19712100 年之间的有效日期。那么可以先算出给出的日期与 1970 年 12 月 31 日之间一共有多少天,然后取 模 7 的余数即可得到星期几。

详解

  1. 先算出 1970 年 12 月 31 日距今一共有多少天

  2. 然后对得到的天数模 7 取余数,得到一个数字如 5 ,表示当前是星期五

  3. 最后根据得到的数字输出英文的星期几

代码

const dayOfTheWeek = function (day, month, year) {
const Month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
const Week = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];
// 1970年12月31日为星期四,即初始值为4
let count = 4;
// 算上此年前每年的日期,都先当365天算
count += (year - 1970 - 1) * 365;
// 算上此月前每个月的日期
for (let i = 1; i < month; i++) {
count += Month[i - 1];
}
// 算上此月的日期
count += day;
// 加上今年之前的闰年天数
for (let y = 1971; y <= year - 1; y++) {
if ((y % 4 === 0 && y % 100 !== 0) || y % 400 === 0) {
count++;
}
}
if ((year % 4 === 0 && year % 100 !== 0) || year % 400 === 0) {
if (month > 2) {
count++;
}
}
return Week[count % 7];
};

复杂度分析

  • 时间复杂度:O(n)O(n) 对于任意一个年月日,计算此月前每个月的日期里的循环体需要执行 nn 次,计算加上今年之前的闰年天数里的循环体需要执行 nn 次,其它计算需要各执行 1 次。因此函数执行次数为 f(n)=2n+xf(n) = 2n + x,其中 xx 为正整数常数。问题规模属于线性阶,故时间复杂度为 O(n)O(n)

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

    此算法需要分配的空间主要为 Month 和 Week 数组,分别需要存放 12 和 7 个常量节点。空间占用属于常数阶,故空间复杂度为 O(1)O(1)

方法二 巧用 JS 库函数法

思路

JS 库提供了一系列的函数。借助以下函数,我们可以得到任意一个符合题目说明的日期是星期几。

Date.parse(datestring);
// 解析一个日期时间字符串(datestring),并返回 1970/1/1 午夜距离该日期时间的毫秒数。
var Date = new Date();
// 初始化当前的日期和时间
Date.getDay();
// 获取当前星期X(0-6,0代表星期天)

详解

  1. 先调用 Date.parse() 方法得到给定日期的时间戳

  2. 再调用 new Date() 方法得到给定时间戳的日期和时间

  3. 再调用 Date.getDay() 方法得到一个数字如 5 ,表示当前是星期五

  4. 最后输出英文的星期几

代码

const dayOfTheWeek = function (day, month, year) {
const date = new Date(Date.parse(`${year}/${month}/${day}`));
const Week = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];
return Week[date.getDay()];
};

复杂度分析

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

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

有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。 1. 数字 1-9 在每一行只能出现一次。 2. 数字 1-9 在每一列只能出现一次。 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例

输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false

解释: 以上两个例子中,除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

  • 一个有效的数独(部分已被填充)不一定是可解的。

  • 只需要根据以上规则,验证已经填入的数字是否有效即可。

  • 给定数独序列只包含数字 1-9 和字符 '.'

  • 给定数独永远是 9x9 形式的。

方法一 利用哈希表

思路

用一个哈希对象记录每一个数字是否在当前行 / 列 / 子数独已存在,若已存在,则为无效数独

详解

  1. 维护三个记录数独单元格元素的哈希对象

  2. 以行 / 列 / 子数独 三种方式遍历数据每一个单元格,

  3. 如果出现重复,返回 false。

  4. 如果没有,则保留此值以进行进一步跟踪。

const isValidSudoku = function (board) {
for (let i = 0; i < 9; i++) {
// 行
const rowMap = {};
// 列
const colMap = {};
// 子数独
const sqreMap = {};
for (let j = 0; j < 9; j++) {
const rowEle = board[i][j];
const colEle = board[j][i];
// 行内是否存在重复
if (rowEle !== '.') {
if (rowMap[rowEle]) {
return false;
}
rowMap[rowEle] = 1;
}
// 列内是否存在重复
if (colEle !== '.') {
if (colMap[colEle]) {
return false;
}
colMap[colEle] = 1;
}
// 每一个子数独内是否存在重复
const R = Math.floor(i / 3) * 3 + Math.floor(j / 3);
const C = Math.floor(3 * (i % 3) + j % 3);
const sqreEle = board[R][C];
if (sqreEle !== '.') {
if (sqreMap[sqreEle]) {
return false;
}
sqreMap[sqreEle] = 1;
}
}
}
return true;
};

复杂度分析

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

    因为只对 81 个单元格进行了一次迭代。

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

方法二 位运算

思路

使用一个9位二进制数判断数字是否被访问,第k位数为1代表k已存在,为0代表k不存在

详解

更新方式(记九位数为row,传入的数字为rowEle):

  • 判断是否加入:将row右移位rowEle位,与1进行与运算

    • 结果为0:未加入,将rowEle加入row

    • 结果为1:已加入,返回false

  • 将传入的数字加入row:将1左移位rowEle位,与row异或

    例子:对于数字1010101000,其第3,5,7,9位为1,表示当前3,5,7,9已经存在

  • 新来数字为2:

    • 1010101000右移2位得到10101010,与1进行与运算,结果为0,2不存在。

    • 将1左移2位得到100,异或后得到1010101100

  • 新来数字为4:

    • 1010101000右移3位得到1010101,与1进行与运算,结果为1,3已经存在。

    • 返回false

列,子数独同上

const isValidSudoku = function (board) {
let row = 0;
let col = 0;
let sqre = 0;
for (let rIndex = 0; rIndex < 9; rIndex++) {
row = col = sqre = 0;
for (let cIndex = 0; cIndex < 9; cIndex++) {
const rowEle = board[rIndex][cIndex];
const colEle = board[cIndex][rIndex];
const R = Math.floor(rIndex / 3) * 3 + Math.floor(cIndex / 3);
const C = Math.floor(3 * (rIndex % 3) + cIndex % 3);
const sqreEle = board[R][C];
if (!isNaN(rowEle)) {
row = ((row >> rowEle) & 1) === 1 ? -1 : row ^ (1 << rowEle);
}
if (!isNaN(colEle)) {
col = ((col >> colEle) & 1) === 1 ? -1 : col ^ (1 << colEle);
}
if (!isNaN(sqreEle)) {
sqre = ((sqre >> sqreEle) & 1) === 1 ? -1 : sqre ^ (1 << sqreEle);
}
if (row === -1 || col === -1 || sqre === -1) {
return false;
}
}
}
return true;
};

复杂度分析

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

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

除本身之外的数组之积

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例

输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

方法一

思路

看完题目最直接的一个想法是,先遍历一遍数组求出所有数字之乘积,然后除以对应位置的上的数字即可。但是,这道题的关键在于,不能使用除法,并且要求时间复杂度为 O(n)。所以,我们稍微调整下思路,将乘积分成 2 部分,先计算出当前数字的左侧数字乘积,然后计算出当前数字的右侧数字乘积,最后将 2 部分乘积相乘即可。

详解

  1. 第一步,定义一个数组 leftProduct,用于存放当前数字的左侧数字乘积。通过循环遍历,依次相乘,计算出当前数字的左侧数字乘积。

  2. 第二步,定义一个数组 rightProduct,用于存放当前数字的右侧数字乘积。同理,依次计算出当前数字的右侧数字乘积。

  3. 第三步,将每个数字的左侧乘积和右侧乘积对应相乘,即可得到最终的结果。

代码

/**
* @param {number[]} nums
* @return {number[]}
*/
const productExceptSelf = (nums) => {
const len = nums.length;
const result = [];
const leftProduct = []; // 存储当前数字的左侧数字乘积
const rightProduct = []; // 存储当前数字的右边侧数字乘积
leftProduct[0] = 1;
rightProduct[len - 1] = 1;
// 计算左侧数字的乘积
for (let i = 1; i < len; i += 1) {
leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
}
// 计算右侧数字的乘积
for (let j = len - 2; j >= 0; j -= 1) {
rightProduct[j] = rightProduct[j + 1] * nums[j + 1];
}
// 左侧数字的乘积 * 右侧数字的乘积
for (let k = 0; k < len; k += 1) {
result[k] = leftProduct[k] * rightProduct[k];
}
return result;
};

复杂度分析

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

    上述解法中,使用了 3 个单层 for 循环,时间复杂度和数组个数 n 线性相关,因此,时间复杂度为 O(n)O(n)

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

    上述解法中,申请了 3 个大小为 n 的数组空间,因此,空间复杂度为O(n3)O(n*3),即 O(n)O(n)

方法二

思路

对于第一种解法,我们可以再进行下优化,将后面2个循环合并下。先计算出左侧数字的乘积,直接放到结果数组 result 中,然后用变量 right 存储每个数字右侧的乘积,并且进行累积相乘,就可以得到最终的结果了。

详解

  1. 第一步,定义一个数组 result,用于存放当前数字的左侧数字乘积。通过循环遍历,依次相乘,计算出当前数字左侧的乘积。

  2. 第二步,定义一个变量 right,存储每个数字右侧的乘积,并且进行累积相乘,即可得到最终结果。

代码

/**
* @param {number[]} nums
* @return {number[]}
*/
const productExceptSelf = (nums) => {
const len = nums.length;
const result = [1];
let right = 1;
// 计算左侧数字的乘积,存到 result 中
for (let i = 1; i < len; i += 1) {
result[i] = result[i - 1] * nums[i - 1];
}
// 用变量 right 存储每个数字右侧的乘积,并且进行累积相乘
for (let j = len - 1; j >= 0; j -= 1) {
result[j] *= right;
right *= nums[j];
}
return result;
};

复杂度分析

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

    上述解法中,使用了 2 个单层 for 循环,时间复杂度和数组个数 n 线性相关,因此,时间复杂度为 O(n)O(n)

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

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

存在重复元素

给定一个整数数组,判断是否存在重复元素。

如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

示例1

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

示例2

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

示例3

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

方法一 暴力循环法

思路

暴力循环法很简单,排序数组,判断前后两个数字是否相等,只要有相等的情况,那就返回 true ,直到循环全部数组,没有就返回 false

详解

  1. 对原数组进行排序,按照从小到大排序

  2. 设置默认结果是 false

  3. 遍历数组,当遍历到的数据和下一个将要遍历的数据做比较,判断是否相同,相同则返回 true ,否则返回 false

/**
* @param {number[]} nums
* @return {boolean}
*/
const containsDuplicate = function (nums) {
// 按照从小到大的顺序进行排序
nums.sort((a, b) => a - b);
let res = false;
nums.forEach((i, index) => {
// 防止数组下标越界,因为要取第index + 1位的数据
if (index < nums.length - 1) {
// 进行或运算,当有相等的时候,res设置位true
res = res || (i === nums[index + 1]);
}
});
return res;
};

复杂度分析

  • 时间复杂度: O(nlogn)O(n * logn)

    对于每个元素,首先通过排序确定数组从小到大的顺序,构造一个从小到大展示的数组,比如[1,1,2,3],再通过对比前后两位的数字是否相等,这将耗费 O(nlogn)O(n * logn) 的时间。

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

    对于数组,无论循环多少遍,空间占用永远只有一个 res ,所以空间复杂度是 O(1)O(1)

方法二 转化Set法

思路

通过 js 的 API 转化为 Set,然后比较原数组和Set的长度来判断是否有相等的数字

详解

1.对原数组转化为 Set 去重 2.再把Set转化成 Array 3.比较两个 Array 的长度是否相等,相等就说明没有重复的数据

/**
* @param {number[]} nums
* @return {number}
*/
const containsDuplicate = function (nums) {
// 转化为Set来去重
const newArr = Array.from(new Set(nums));
return newArr.length !== nums.length;
};

复杂度分析

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

    会有1次遍历数组,所以最终的时间复杂度是 O(n)O(n)

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

    因为要一个数组的辅助存储空间,所以空间复杂度是 O(n)O(n)