Day01 第一章数组 part01

# 一，数组理论基础

文章链接：https://programmercarl.com/ 数组理论基础.html

这部分都是一些基础知识。

知识点：

1. 数组是存放在连续内存空间上的相同类型数据的集合。

2. 数组的下标从 0 开始

3. 内存空间连续

4. 数组元素只能覆盖不能删除

# 704 二分查找

视频链接：https://www.bilibili.com/video/BV1fA4y1o715/?spm_id_from=333.999.0.0&vd_source=e0e7d9473b1926d5432c3c9db17fd187

二分查找：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

# 题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

易错点：边界

解决：左闭右闭是 left=right 是合法区间，所以对 <=，且 midlle 要 -+1。反之。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int search(int[] nums, int target) {
    int left=0,right= nums.length-1;
    int middle;
    while(left<=right){
        middle=(left+right)/2;
      if(target>nums[middle]){
            left=middle+1;

        }else if(target<nums[middle]){
            right=middle-1;
        }else return middle;
    }
    return -1;
}

# 27 移除元素

文章链接：https://programmercarl.com/0027. 移除元素.html# 思路

# 题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O (1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

# 1. 暴力解法

解释：找到要删除的值就将后面的值赋值给前面。用两层 for 循环。

代码实现：

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 count = nums.length,k;
        for (int i = 0; i < count; i++) {

           if (nums[i]==val) {
                
                for (int j = i; j < count-1; j++) {
                    nums[j] = nums[j + 1];

                }
                i--;
                count--;
            }
        }
        return count;
    }
}

易错点：i 要自减，否则会导致其中一个元素没有对比到

# 2. 双指针解法

# 双指针法

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

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置

代码实现：

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,fastIndex;
        for(fastIndex=0;fastIndex<nums.length;fastIndex++){
            if(nums[fastIndex]!=val){
                nums[slowIndex]=nums[fastIndex];
                slowIndex++;
            }
            
        }
        return slowIndex;
    }
}

易错点：return 的时候 slowIndex 不需要 + 1，最后一次它会自增。

# 总结

今天我学到了二分查找法和双指针，其实以前看过但没注意细节，有些也忘了，复习一遍挺好的。学习了三个小时，不包括研究 hexo 博客。