Post

数组算法学习

Posted Updated
By Kurisu 22 min read

二分查找

二分查找

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

该题问题在于边界的处理，到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。区间的定义这就决定了二分法的代码应该如何写。区间的定义就是不变量，要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

  1. 写法一[left, right]
    • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
    • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
  2. 写法二[left, right)
    • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
    • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

代码示例：

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
33
34
35
36
37
38
39
40
41

// 版本一
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

// 版本二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

双指针

移除元素

问题：移除数组元素，给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

数组中的元素具有无法单纯删除，只能覆盖的特点。

  1. 暴力解法
    两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组，一层循环找到目标值元素后，第二次循环依次将后面所有元素向前移动一个位置，并将最后的元素覆盖为目标值，时间复杂度较高。
  2. 快慢指针
    通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，很多考察数组、链表、字符串等操作的面试题，都使用双指针法，要明确快慢指针各自的含义！
    • 快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
    • 慢指针：指向更新新数组下标的位置

一种思路是有多少个目标值，就将后面所有的元素往前移进多少位，一个指针负责指向更新新数组下标的位置，快指针就寻找右方不为目标值的元素，在移进过程中不断更新；另一种思路是在左边找目标值，替换右边不为目标值的元素，确保目标值整体都在右方。

二刷思考：双指针中在对左右指针进行移动时，最好是确保移动完毕后重新开始循环，进行一次循环条件的判断，不然在边界情况容易出现数组越界等问题。

代码示例：

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

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

//相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

有序数组的平方

问题：给一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序，该问题关键在于正负数平方后大小关系可能会发生改变。

  1. 暴力解法
    先全部平方覆盖，在对数组做整体排序。时间复杂度是 O(n + nlogn)
  2. 左右指针
    要点在于数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法，i指向起始位置，j指向终止位置，同时定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置，将左右两边最大数填入新数组。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}

三数之和

问题：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

我在哈希表算法学习中在一道类似的题中提到过三数之和，哈希法对于该题去重过于麻烦，双指针法是一种更好的解决方案。先整体升序排序，以nums[i]为循环索引，在其右边寻找nums[j]和nums[k]表示为nums[left]和nums[right]，初始为最左边和最右边，若和<0则将left右移，和>0则将right左移，直到找到和为0的三元组。

需要注意的是，返回的三元组是要求值不重复，这就需要我们碰到类似-1,-1,-1,2这种情况时，去掉重复-1,-1,2三元组，要点就是在得到和为0的三元组后，跳过左右相邻的重复的元素。

二刷思考：对于双指针的执行过程还是有一点理解不到位，再就是对于去重的边界判断掌控不好，只考虑到了去重，但没有考虑到需要进行一次判断后再去去重，去重掉的元素有可能是会继续构成一个三元组的。

代码示例：

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
33
34
35
36
37
38

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0)
                return ans;
            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] < 0)
                {
                    left++;
                    continue;
                }
                if(nums[i] + nums[left] + nums[right] > 0)
                {
                    right--;
                    continue;
                }
                if(nums[i] + nums[left] + nums[right] == 0)
                {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(right > left && nums[left] == nums[left+1])  //去重b
                        left++;
                    while(right > left && nums[right] == nums[right-1])  //去重c
                        right--;
                    right--; 
                    left++;
                }
            }
        }
        return ans;
    }
}

四数之和

问题：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

也就是三数之和再加一层循环，没有什么需要多说的，注意细节吧。

代码示例：

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
33
34
35
36
37
38
39

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);

        if(nums.length < 4)
            return ans;

        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i-1]) //确保判断一次再进行去重
                continue;

            for(int j = i + 1; j < nums.length; j++){
                if(j > i + 1 && nums[j] == nums[j-1])
                    continue;

                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target)
                        left++;
                    if(sum > target)
                        right--;
                    if(sum == target){
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while(left < right && nums[left] == nums[left+1])
                            left++;
                        while(left < right && nums[right] == nums[right-1])
                            right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

接雨水

问题：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

我们按列来计算，该列能盛放多少水其实完全取决于左右最高处相对又较矮的那一个高度。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        leftMax[0] = height[0];
        rightMax[height.length - 1] = height[height.length - 1];
        int sum = 0;
        for(int j = 1; j < height.length; j++) {
            leftMax[j] = Math.max(height[j], leftMax[j-1]);
        }
        for(int j = height.length - 2; j > 0; j--) {
            rightMax[j] = Math.max(height[j], rightMax[j+1]);
        }
        for(int i = 1; i < height.length - 1; i++) {
            sum += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return sum;
    }
}

滑动窗口

长度最小的子数组

问题：给定一个含有n个正整数的数组和一个正整数target，找出该数组中满足其总和大于等于 target的长度最小的子数组[numsl, numsl+1, …, numsr-1, numsr]，并返回其长度，如果不存在符合条件的子数组，返回0。

  1. 暴力解法
    两层循环，遍历所有子数组找到长度最小的符合条件的子数组，不断更新答案，一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。
  2. 滑动窗口
    实现滑动窗口，主要确定如下三点：窗口内是什么？如何移动窗口的起始位置？如何移动窗口的结束位置？本题中窗口就是满足其和大于等于s的长度最小的连续子数组，如果当前窗口的值大于等于s了，窗口起始位置就要向前移动了，窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
    解题的关键就在于窗口的起始位置如何移动，滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置，优化掉了没必要进行判断的子数组，从而将O(n^2)暴力解法降为O(n)。

二刷思考：滑动窗口一般以窗口结束位置为索引，我不禁在思考如果用起始位置为索引又如何呢,为什么就不能用起始位置为索引，结束位置再用一个指针来滑动呢，于是我就开始尝试，发现在实现的过程中会碰到各种各样的问题，需要改用while，最后效果其实和for循环无异，还是按照统一的思路来解决吧。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

模拟

螺旋矩阵II

问题：给你一个正整数n，生成一个包含1到n2所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。

求解本题依然是要坚持循环不变量原则,我们模拟顺时针画矩阵的过程: 填充上行从左到右 –> 填充右列从上到下 –> 填充下行从右到左 –> 填充左列从下到上，这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来，即拐角交由哪条边进行处理，我们以左闭右开为例进行解题。

模拟题给我的感觉是要熟悉对于数据结构的操作方法，属于是熟能生巧的一类题，我遇到的问题主要在于不知道循环的终止条件为什么比较好，以及对于奇偶需要进行分类讨论，题解给出了比较好的详细解决方案。

代码示例：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {

            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }
}
学习, 算法
算法
This post is licensed under CC BY 4.0 by the author.

Trending Tags

算法 ACG 技术 生活 小记