面试经典150题刷题记录

数组部分

1. 合并两个有序的子数组 —— 倒序双指针避免覆盖

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

参考题解：. - 力扣（LeetCode）

class Solution {
    
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        /* 
            倒序双指针法：从尾部开始，从而避免覆盖问题 
            m,n 分别表示 nums1 和 nums2 的元素个数
        */  
        int p1 = m - 1; // 指向第一个数组的最后一个元素
        int p2 = n - 1; // 指向第二个元素数组的最后一个元素
        int insert_position = m + n - 1; // 指向要插入的位置
        while (p2 >= 0) { // nums2 还有要合并的元素
            // 如果 p1 < 0，那么走 else 分支，把 nums2 合并到 nums1 中
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[insert_position--] = nums1[p1--]; // 填入 nums1[p1]
            } else {
                nums1[insert_position--] = nums2[p2--]; // 填入 nums2[p1]
            }
        }
    }
}

2. 移除元素 —— 数组末尾元素交换法

27. 移除元素

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

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

class Solution {
    public int removeElement(int[] nums, int val) {
        /**
            idea & steps:
                1. 从左往右遍历数组nums，，
                2. 如果与val相同，则与数组最后一个元素交换，
                3. 数组长度 -- 
                4. 注：如果相同了则继续遍历当前元素；（因为当前元素是末尾交换过来的元素，不一定不等于val）
                5. 结束的条件：当前判断的位置与更改后的数组位置相同
         */
        int cur = 0;  // 起始指针
        int rear = nums.length - 1; // 终止指针
        while(cur <= rear) {
            if(nums[cur] == val) {
                nums[cur] = nums[rear];
                rear --;
            }else {
                cur ++;
            }
        }
        return cur;
    }
}