LeetCode力扣面试经典150题详细题解 (1~5) 持续更新中-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode力扣面试经典150题详细题解 (1~5) 持续更新中。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.合并两个有序数组

2.移动元素

3.删除有序数组中的重复项

4.删除排序数组中的重复项 II

5.多数元素

暂时更新到这里，博主会持续更新的

1.合并两个有序数组

题目（难度：简单）：

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

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

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

解法一：

思路：先合并两个数组，然后通过冒泡排序进行排序

public void merge(int[] nums1, int m, int[] nums2, int n) {  
      
    // 获取nums1数组的长度  
    int length1 = nums1.length;  
      
    // 从nums1的有效元素末尾开始，将nums2的所有元素复制到nums1的剩余空间  
    for (int i = m; i < length1; i++) {  
        nums1[i] = nums2[i - m];  
    }  
      
    // 从nums1的开头开始，进行冒泡排序，以确保整个nums1数组是有序的  
    for (int i = 0; i < length1 - 1; i++) {  
        if (nums1[i] > nums1[i + 1]) {  
            // 如果当前元素大于其相邻的元素，则交换它们  
            int tmp = nums1[i];  
            nums1[i] = nums1[i + 1];  
            nums1[i + 1] = tmp;  
        }  
    }  
      
}

解法二：

思路：数组nums1和nums2通过比较的方式填充nums1末尾

   public void merge(int[] nums1, int m, int[] nums2, int n) {  
    // 初始化指向nums1和nums2末尾的指针  
    int i = m - 1;  // nums1中有效数据的最后一个索引  
    int j = n - 1;  // nums2中有效数据的最后一个索引  
    // 初始化指向nums1最终位置的指针  
    int k = nums1.length - 1; // nums1的末尾索引，也是合并后数组的末尾索引  
  
    // 当nums2中还有元素未处理时执行循环  
    while (j >= 0) {  
        // 如果nums1中还有元素，并且当前nums1元素大于nums2元素  
        if (i >= 0 && nums1[i] > nums2[j]) {  
            // 将nums1当前元素放到最终位置，并将指针向前移动  
            nums1[k--] = nums1[i--];  
        } else {  
            // 否则，将nums2当前元素放到nums1的最终位置，并将指针向前移动  
            nums1[k--] = nums2[j--];  
        }  
    }  
    // 循环结束后，nums1包含了合并后的有序数组  
}

2.移动元素

题目（难度：简单）：

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

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

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

解法一：文章来源地址https://www.toymoban.com/news/detail-825461.html

public int removeElement(int[] nums, int val) {  
    int length = 0; // 用于记录非目标值元素的数量，也即新数组的长度  
    for (int i = 0; i < nums.length; i++) {  
        // 如果当前元素不等于目标值val  
        if (nums[i] != val) {  
            // 将该元素移动到数组的前端（覆盖length位置上的元素）  
            nums[length] = nums[i];  
            // 更新非目标值元素的数量  
            length++;  
        }  
        // 如果当前元素等于目标值val，则不做任何操作，直接跳过  
    }  
    // 返回新数组的长度  
    return length;  
}

解法二：

public int removeElement(int[] nums, int val) {  
    // 初始化右指针j为数组末尾的索引  
    int j = nums.length - 1;  
    // 遍历数组，左指针i从数组开始位置到j之前的位置  
    for (int i = 0; i < j; i++) {  
        // 如果当前元素等于目标值val  
        if (nums[i] == val) {  
            // 交换当前元素nums[i]与右指针指向的元素nums[j]  
            int tmp = nums[i];  
            nums[i] = nums[j];  
            nums[j] = tmp;  
            // 由于已经交换了一个等于val的元素到数组末尾，所以j向左移动一位  
            j--;  
            // 由于交换后当前位置的元素可能又变成了需要移除的值，所以i也需要向左移动一位  
            i--;  
        }  
    }  
    // 返回j+1作为新数组的长度，因为j此时指向最后一个有效元素的下一个位置  
    return j + 1;  
}

3.删除有序数组中的重复项

题目（难度：简单）：

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

解法一：

public int removeDuplicates(int[] nums) {  
    // 使用双指针p和q，p指向当前不重复序列的末尾，q用于遍历数组  
    int p = 0;  
    int q = 1;  
    // 当q指针未到达数组末尾时执行循环  
    while (q < nums.length) {  
        // 如果当前p和q指向的元素不相等，说明找到了一个新的不重复元素  
        if (nums[p] != nums[q]) {  
            // 如果q和p之间的元素个数大于1，说明有多个重复元素  
            // 此时，将q指向的元素复制到p的下一个位置，覆盖掉多余的重复元素  
            if (q - p > 1) {  
                nums[p + 1] = nums[q];  
            }  
            // p指针前移一位，指向新的不重复序列的末尾  
            p++;  
        }  
        // q指针前移一位，继续遍历数组  
        q++;  
    }  
    // 返回新的数组长度，即p+1（因为p指向的是最后一个不重复元素的下一个位置）  
    return p + 1;  
}

4.删除排序数组中的重复项 II

题目（难度：中等）：

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解法一：

public int removeDuplicates(int[] nums) {  
    // 获取数组的长度  
    int length = nums.length;  
      
    // 初始化指针p和q  
    // p指向新数组的最后一个已处理元素之后的位置  
    // q从数组的第三个元素开始遍历（索引为2）  
    int p = 0;  
    int q = 2;  
      
    // 当q指针还没有遍历完整个数组时，继续执行循环  
    while (q < length) {  
        // 如果p指针指向的元素与q指针指向的元素不同  
        // 说明找到了一个新的、不重复的元素  
        if (nums[p] != nums[q]) {  
            // 将这个新元素复制到p指针之后的位置  
            // 因为p指针指向的是新数组的最后一个已处理元素之后的位置  
            // 所以新元素应该放在p+2的位置（因为p+1的位置是留给下一个不重复元素的）  
            nums[p + 2] = nums[q];  
              
            // 将p指针前移一位，为下一个不重复元素腾出空间  
            p++;  
        }  
          
        // q指针无论如何都前移一位，继续遍历数组  
        q++;  
    }  
      
    // 返回新数组的长度  
    // 由于数组索引是从0开始的，所以新数组的长度是p+2  
    // 其中p是新数组的最后一个已处理元素的位置，所以p+2是新数组的长度  
    return p + 2;  
}

5.多数元素

题目（难度：简单）：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解法一：

public int majorityElement(int[] nums) {  
        // 初始化候选元素和计数器  
        int candidate = nums[0]; // 将候选元素初始化为数组的第一个元素  
        int count = 0;           // 计数器  
  
        // 遍历数组  
        for (int num : nums) {  
            // 如果计数器为0，则当前元素为候选元素，并将计数器设为1  
            if (count == 0) {  
                candidate = num;  
                count = 1;  
            }  
            // 如果当前元素与候选元素相同，则计数器加1  
            else if (num == candidate) {  
                count++;  
            }  
            // 如果当前元素与候选元素不同，则计数器减1  
            else {  
                count--;  
            }  
        }  
  
        // 返回候选元素，即为多数元素  
        return candidate;  
    }