【每日算法Day 16】数组基础2
数组的旋转、翻转（限制额外空间），可用作哈希的特性。
# LeetCode 189. 旋转数组 (opens new window)
# 题目描述
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
# 示例
输入:
[1,2,3,4,5,6,7] 和 k = 3
输出:
[5,6,7,1,2,3,4]
2
3
4
# 解题思路
可以使用暴力法，每次将数组移动1位，共移动k%n次。暴力法的时间复杂度为O(n*(k%n))，空间复杂度为O(1)。
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0) return;
for(int i=0;i<k%nums.length;i++){
int tail=nums[nums.length-1];
for(int j=nums.length-1;j>0;j--){
nums[j]=nums[j-1];
}
nums[0]=tail;
}
}
2
3
4
5
6
7
8
9
10
还可以使用同等大小的空间存储最终的结果。记k%n=m，则移动之后第0~(n-1-m)个元素被移动到数组尾部，第(n-m)~n-1个元素被移动至数组头部。该方法的时间复杂度为O(2n)，空间复杂度为O(n)。
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0) return;
int n=nums.length;
int m=k%n;
int[] temp=new int[n];
for(int i=0;i<n;i++){
if(i<=n-1-m){
temp[i+m]=nums[i];
}else{
temp[i-(n-m)]=nums[i];
}
}
for(int i=0;i<n;i++){
nums[i]=temp[i];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
进一步为了不使用额外O(n)的空间，可以使用两次分块翻转数组的方法。正如上面所说则移动之后第0~(n-1-m)个元素被移动到数组尾部，第(n-m)~n-1个元素被移动至数组头部。首先翻转一次数组，则(n-1-m)~0个元素被移动到数组尾部，n-1~(n-m)个元素被移动至数组头部。再分别对这两块进行翻转即可。该方法时间复杂度为O(2n)，空间复杂度为O(1)。
public void rotate(int[] nums, int k) {
reverse(nums,0,nums.length-1);
reverse(nums,0,k%nums.length-1);
reverse(nums,k%nums.length,nums.length-1);
}
private void reverse(int[] nums,int left,int right){
for(;left<right;left++,right--){
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# LeetCode 41. 缺失的第一个正数 (opens new window)❤
# 题目描述
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
# 示例
输入: [1,2,0]
输出: 3
输入: [3,4,-1,1]
输出: 2
2
3
4
5
# 解题思路
想要没有出现的最小正整数x增加，则从1~x-1的所有值都必须存在于数组中，而长度为n的数组中最多能存1~n这n个的连续正整数，则x最大值为n+1。x的取值区间为[1,n+1]，而恰好原数组长度为n，则可以用原数组作为哈希数组。
哈希函数为f(nums[i])=nums[i]-1，数组中nums[i]如果等于i+1则表示i+1存在于数组中，不等于i+1表示数组中没有i+1这个数。
public int firstMissingPositive(int[] nums) {
int n=nums.length;
//for循环结束时保证整个数组中在答案取值范围内的数x都在nums[x-1]的位置
for (int i = 0; i < n; i++) {
//while循环结束时能保证当前的nums[i]要么在答案取值范围外，要么和下标吻合哈希性质(即nums[i]==i+1)
//nums[i] != nums[nums[i] - 1]是为了避免重复数字造成的死循环例如[-1,3,3,4]
while (nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
//当前的nums[i]在答案的取值范围内不等于i-1时，把nums[i]和nums[nums[i]-1]交换
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; i++) {
if (nums[i]!=i+1)
return i+1;
}
return n+1;
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# LeetCode 299. 猜数字游戏 (opens new window)
# 题目描述
你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。你的朋友将会根据提示继续猜，直到猜出秘密数字。
请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。
请注意秘密数字和朋友的猜测数都可能含有重复数字。你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。
# 示例
示例 1:
输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
示例 2:
输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。
2
3
4
5
6
7
8
9
# 解题思路
可以使用额外的O(n)空间保存：HashMap保存secret当中不被guess匹配的字符与个数+ArrayList保存guess当中不匹配的所有字符。遍历两遍，第一遍找到匹配的数字增加bull计数，第二遍比较map和list计算cows的数量。时间复杂度为O(n)。
public String getHint(String secret, String guess) {
Map<Character,Integer> map=new HashMap<>();
List<Character> list=new ArrayList<>();
int bulls=0,cows=0;
for (int i = 0; i < secret.length(); i++) {
char s=secret.charAt(i),g=guess.charAt(i);
if (s == g) {
bulls++;
} else {
list.add(g);
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else {
map.put(s, 1);
}
}
}
for (Character c : list) {
if (map.containsKey(c) && map.get(c)>0) {
cows++;
map.put(c,map.get(c)-1);
}
}
return bulls+"A"+cows+"B";
}
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
小优化:由于输入只含有'0'-'9'因此可用两个bucket：int[10]代替HashMap，数组下标为key，值为计数。另一个int[10]存储猜错位置的各数字的计数，对比两个数组的每个位置取两者的最小值累加到cows中。
public String getHint(String secret, String guess) {
int[] bullsBucket=new int[10];
int[] cowsBucket=new int[10];
int bulls=0,cows=0;
for (int i = 0; i < secret.length(); i++) {
char s=secret.charAt(i),g=guess.charAt(i);
if (s == g) {
bulls++;
} else {
cowsBucket[g-'0']+=1;
bullsBucket[s-'0']+=1;
}
}
for (int i=0;i<10;i++) {
cows+=Math.min(bullsBucket[i],cowsBucket[i]);
}
return bulls+"A"+cows+"B";
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19