数组理论基础
数组存放在连续内存空间上的相同类型数据的集合
数组下标从0开始
数组内存空间的地址是连续的
Java 二维数组排布不是连续的
704 二分查找
Link
Leetcode 704
考虑二分法的时机
数组有序，且无重复元素 （如果有重复元素，注意滑动窗口）
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution{
public int binarySearch(int[] nums, int target){
if(target < nums[0] || target > nums[nums.length - 1]){
return -1
}
int left = 0, right = nums.length-1;
while(left <= right){
int mid = left + ((right - left) >> 1);
if (nums[mid] == target){
return mid;
} else if (nums[mid] < target){
left = mid + 1;
} else if (nums[mid] > target){
right = mid - 1;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution{
public int binarySearch(int[] nums, int target){
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0, right = nums.length;
while(left < right){
int mid = left + ((right - left) >> 1);
if (nums[mid] == target){
return mid;
} else if (nums[mid] < target){
left = mid + 1;
} else if (nums[mid] > target){
right = mid;
}
}
return -1;
}
}
|
循环不变量原则
注意右区间相关区别
- 设置右起始值
- 更新右值有区别
- while条件的区别
27 移除元素
Link
Leetcode 27
移除元素
数组元素删除过程复杂，因为数组长度不能更改，需要注意
实现
- 暴力解法
- 查到val之后，把剩余元素用for loop向前覆盖一位
- size自减1
- i不自增，重新检查覆盖之后的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution{
public int removeElement(int[] nums, int val){
int size = nums.length;
for(int i = 0; i < size; i++){
if(nums[i] == val){
for(int j = i + 1; j < size; j++){
nums[j-1] = nums[j];
}
size--;
i--;
}
}
return size;
}
}
|
- 快慢同向指针
- 如果快指针找到val，慢指针不变
- 如果快指针没找到val，慢指针位置被快指针位置元素覆盖，慢指针向下移一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution{
public int removeElement(int[] nums, int val){
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
if(val != nums[fastIndex]){
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
}
|
- 相向双指针
- 右指针移到不是val的位置
- 右指针的val覆盖左指针是val的位置
需要两个while循环 查找右指针第一个指向不是val的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution{
public int removeElement(int[] nums, int val){
int left = 0, right = nums.length - 1;
while(right >= 0 && nums[right] == val) right--;
while(left <= right){
if (nums[left] == val){
nums[left] = nums[right--];
}
left++;
while(right >= 0 && nums[right] == val) right--;
}
return left;
}
}
|
不需要两个while循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution{
public int removeElement(int[] nums, int val){
int left = 0, right = nums.length - 1;
while(left <= right){
if(nums[left] == val){
nums[left] = nums[right];
right--;
} else {
left++;
}
}
return left;
}
}
|
记得更新右指针的位置