【Leetcode算法题】372. 超级次方

By Long Luo

今天Leetcode的每日一题是:372. 超级次方,题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
372. 超级次方

你的任务是计算a^b对1337取模,a是一个正整数,b是一个非常大的正整数且会以数组形式给出。

示例 1:
输入:a = 2, b = [3]
输出:8

示例 2:
输入:a = 2, b = [1,0]
输出:1024

示例 3:
输入:a = 1, b = [4,3,3,8,5,2]
输出:1

示例 4:
输入:a = 2147483647, b = [2,0,0]
输出:1198

提示:
1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导0

方法一:暴力

思路与算法:

首先想到的是暴力法: 直接2个循环,判断是否存在相同数字。

但会超时,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
if (Math.abs(i - j) <= k) {
return true;
}
}
}
}

return false;
}

复杂度分析:

  • 时间复杂度:O(n2)O(n^2),其中nn为数组长度。

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

方法二:哈希表

思路与算法:

可以使用哈希表记录每个元素的最大下标。从左到右遍历数组nums\textit{nums},当遍历到下标ii时,进行如下操作:

  • 如果哈希表中已经存在和nums[i]\textit{nums}[i]相等的元素且该元素在哈希表中记录的下标jj满足ijki-j \le k,返回true\text{true}

  • nums[i]\textit{nums}[i]和下标ii存入哈希表,此时iinums[i]\textit{nums}[i]的最大下标。

上述两步操作的顺序不能改变,因为当遍历到下标ii时,只能在下标ii之前的元素中寻找与当前元素相等的元素及该元素的最大下标。

当遍历结束时,如果没有遇到两个相等元素的下标差的绝对值不超过kk,返回false\text{false}

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
int idx = map.get(nums[i]);
if (Math.abs(i - idx) <= k) {
return true;
}
map.put(nums[i], i);
} else {
map.put(nums[i], i);
}
}

return false;
}

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn是数组nums\textit{nums}的长度。需要遍历数组一次,对于每个元素,哈希表的操作时间都是O(1)O(1)

  • 空间复杂度:O(n)O(n),其中nn是数组nums\textit{nums}的长度。需要使用哈希表记录每个元素的最大下标,哈希表中的元素个数不会超过nn

方法三: 滑动窗口

考虑数组nums\textit{nums}中的每个长度不超过k+1k+1的滑动窗口,同一个滑动窗口中的任意两个下标差的绝对值不超过kk。如果存在一个滑动窗口,其中有重复元素,则存在两个不同的下标iijj满足nums[i]=nums[j]\textit{nums}[i]=\textit{nums}[j]ijk|i-j| \le k。如果所有滑动窗口中都没有重复元素,则不存在符合要求的下标。因此,只要遍历每个滑动窗口,判断滑动窗口中是否有重复元素即可。

如果一个滑动窗口的结束下标是ii,则该滑动窗口的开始下标是max(0,ik)\max(0, i-k)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组nums\textit{nums},当遍历到下标ii时,具体操作如下:

如果i>ki>k,则下标ik1i-k-1处的元素被移出滑动窗口,因此将nums[ik1]\textit{nums}[i-k-1]从哈希集合中删除;

判断nums[i]\textit{nums}[i]是否在哈希集合中,如果在哈希集合中则在同一个滑动窗口中有重复元素,返回true\text{true},如果不在哈希集合中则将其加入哈希集合。

当遍历结束时,如果所有滑动窗口中都没有重复元素,返回false\text{false}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length <= 1 || k <= 0) {
return false;
}

int len = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i <= k && i < len; i++) {
if (set.contains(nums[i])) {
return true;
} else {
set.add(nums[i]);
}
}

int left = 0;
int right = left + k;
while (left < right && right < len) {
right++;
set.remove(nums[left]);
left++;
if (right < len) {
if (set.contains(nums[right])) {
return true;
}

set.add(nums[right]);
}
}

return false;
}

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn是数组nums\textit{nums}的长度。需要遍历数组一次,对于每个元素,哈希集合的操作时间都是O(1)O(1)

  • 空间复杂度:O(k)O(k),其中kk是判断重复元素时允许的下标差的绝对值的最大值。需要使用哈希集合存储滑动窗口中的元素,任意时刻滑动窗口中的元素个数最多为k+1k+1个。