源文章：9. 总结篇

数组理论基础

1. 数组理论基础

数组：存放在连续空间上的相同类型数据的集合

  • 数组下标是从0开始的
  • 数据内存空间的地址是连续的
  • 数组元素不能删，只能覆盖

C++中二维数组在地址空间上是连续的。

Java可能是如下排列方式:

算法通关数组3

二分查找

2. 二分查找

【条件】

  • 数组为有序数组
  • 数组中无重复元素

【写法】

  • 左闭右闭区间[ left , right ]

1.while(left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=

2.if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        while(left <= right){
            int mid = left + ((right - left)/2);//(left + right)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] < target){
                left = mid+1;
            }
            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
func search(nums []int, target int) int {
            
        left := 0;
        right := len(nums) -1;
        for left <= right{
            mid := left + ((right - left)/2);//(left + right)/2;
            if(nums[mid] == target){
                return mid
            }
            if(nums[mid] < target){
                left = mid+1;
            }
            if(nums[mid] > target){
                right= mid -1;
            }
        }
        return -1;
}
  • 左闭右开区间 [ left , right )
  1. while( left < right ) ，这里使用 < ，这里left == right是没有意义的，因为是开区间
  2. if (nums[middle] > target) right 更新为 middle，继续遵循左闭右开区间的原则
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int search(int[] nums, int target) {
        int left = 0 ;
        int right = nums.length;
        while(left < right){
            int mid = left +((right - left) >>2);
            if(nums[mid] == target)return mid;
            if(nums[mid] > target) right = mid;
            if(nums[mid] < target) left = mid+1; 
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func search(nums []int, target int) int {
            //左闭右开区间
        left := 0;
        right := len(nums) ;
        for left < right{
            mid := left + ((right - left)>>2);//(left + right)/2;
            if(nums[mid] == target){
                return mid
            }
            if(nums[mid] < target){
                left = mid+1;
            }
            if(nums[mid] > target){
                right= mid;
            }
        }
        return -1;
}

移除元素

【思路】

用后面的数字来覆盖前面的数

  • 暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    //用后面来覆盖前面，集体向前移一位
    //我一开始用错了方法，忘记具体是什么了，大概是nums[j] = nums[j+1]然后i++,这样会导致后面的nums[i]还是等于target但没有被覆盖的现象
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        for(int i = 0 ; i < len ;i++){
            if(nums[i]== val){
                for(int j = i+1 ; j < len;j++){
                    nums[j-1] = nums[j];
                }
                i--;
                len--;
            }
        }
        return len;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func removeElement(nums []int, val int) int {
    len := len(nums);
    for i := 0 ; i < len ;i++{
        if(nums[i] == val){
            for j := i+1 ;j < len ; j++{
                nums[j-1] = nums[j]; 
            }
            len--;
            i--;
        }
    }
    return len;
}
  • 双指针法（快慢指针法）

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    //用后面来覆盖前面，集体向前移一位
    public int removeElement(int[] nums, int val) {
            int slow = 0; 
            for(int fast = 0 ; fast < nums.length; fast++){
                if(nums[fast] != val ){
                    nums[slow++] = nums[fast];  //先赋值再++
                }
            }
            return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0 ; fast <len(nums);fast++{
        if(nums[fast] != val){
            nums[slow]=nums[fast]
            slow++
        }
    }
    return slow;
}

这些实现方法并没有改变元素的相对位置！

  • 相向双指针（类似左闭右闭区间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //用后面来覆盖前面，集体向前移一位
    public int removeElement(int[] nums, int val) {
        //相向双指针
        int left = 0 ; 
        int right = nums.length-1;
        while(left <= right){
            while(left <= right && nums[left] != val){
                ++left;
            }
            while(left <= right && nums[right] == val){
                --right;
            }
            if(left<right){
                nums[left++] = nums[right--];
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func removeElement(nums []int, val int) int {
    left := 0
    right := len(nums) -1
    for left <= right{
        for left <= right &&nums[left]!= val{
            left++
        }
        for left <= right && nums[right] == val{
            right--
        }
        if left < right{
            nums[left] = nums[right]
            left++
            right--
        }
    }
            return left

}