【刷爆LeetCode_01题_合并两个有序数组】

这篇具有很好参考价值的文章主要介绍了【刷爆LeetCode_01题_合并两个有序数组】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法题,好像是不让使用函数

一、题目

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

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

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

1、用例

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。




示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。




示例 3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

二、解法

1)自己写的--有问题

class Solution:
    def merge(self,nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[:] =nums1[0:m]
        nums2[:] =nums2[0:n]
        nums3 = nums1[:] + nums2[:]
        nums1 = nums3.sort()

2)转化成列表,使用sort()函数

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
       
        nums1[:] = nums1[0:m]
        nums2[:] = nums2[0:n]
        nums3 = nums1 + nums2
        nums1[:] = sorted(nums3)
nums1[:] = nums1[0:m] 和 nums2[:] = nums2[0:n] 已经将 nums1 和 nums2 分别裁剪成了只包含前 m 和 n 个元素的列表。

因此,当执行 nums1 + nums2 时,你已经在操作这两个已经被裁剪的列表。在这个特定的上下文中,使用 nums1[:] + nums2[:] (即分别对已经裁剪的 nums1 和 nums2 进行浅拷贝然后合并)和直接使用 nums1 + nums2 合并,效果是一样的,因为无论如何你都是在合并两个已经被裁剪到只包含特定元素的列表。

这种情况下的关键在于,由于 nums1 和 nums2 已经被预处理(裁剪),所以不管是直接合并还是先浅拷贝再合并,最终合并的内容是相同的。


此时,nums3 = nums1 + nums2   =   nums3 = nums1[:] + nums2[:]
解析


实际上,这两段代码在功能上不是完全相同的,主要区别在于它们处理 `nums1` 和 `nums2` 的方式。

在第一段代码中:

```python
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
       
        nums1[:] = nums1[0:m]  # 仅保留nums1中前m个元素
        nums2[:] = nums2[0:n]  # 仅保留nums2中前n个元素
        nums3 = nums1 + nums2  # 将处理后的nums1和nums2合并
        nums1[:] = sorted(nums3)  # 将合并后的列表排序,并更新nums1
```

在这个版本中,`nums1` 和 `nums2` 首先被裁剪到分别只包含其前 `m` 和 `n` 个元素。这对于合并两个已经部分填充的数组来说是必要的,尤其是在涉及到一些特定算法题目时,比如“合并两个有序数组”,其中 `nums1` 有足够的空间来容纳 `nums1` 和 `nums2` 合并后的所有元素,但是初始时只有前 `m` 个元素是有效的,`nums2` 中前 `n` 个元素是有效的。




在第二段代码中:

```python
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
       
        nums3 = nums1 + nums2  # 直接将nums1和nums2合并,没有先裁剪
        nums1[:] = sorted(nums3)  # 将合并后的列表排序,并更新nums1
```

这个版本没有预先裁剪 `nums1` 和 `nums2`,而是直接合并了两个列表。如果 `nums1` 和 `nums2` 的长度正好等于 `m` 和 `n`,这段代码能正确运行。但是,如果 `nums1` 包含额外的、不应该被包含在最终排序结果中的元素(比如一些算法题目中 `nums1` 的后半部分可能被填充了0或其他占位符),这段代码就不能正确地只合并前 `m` 个和前 `n` 个有效元素了。

因此,这两段代码在处理特定情况(尤其是 `nums1` 和 `nums2` 的长度超过了 `m` 和 `n`)时的行为是不同的。正确的选择取决于你的具体需求,尤其是在处理算法和数据结构问题时,第一种方法更为通用和准确。

3)双指针

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 初始化两个数组的最后一个元素的索引,以及nums1的合并位置的索引
        i, j, k = m - 1, n - 1, m + n - 1

        # 当两个数组都还有元素时
        while i >= 0 and j >= 0:
            # 比较两个数组的当前元素,将较大的那个放到nums1的合并位置末尾
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

        # 如果nums2中还有元素没被合并,直接复制到nums1的前面
        # 因为如果nums1的元素已经遍历完,剩下的nums2中的元素一定都比nums1中已经合并的元素小
        while j >= 0:
            nums1[k] = nums2[j]
            k, j = k - 1, j - 1
这段代码的逻辑非常清晰:

初始化指针:使用三个指针i、j、和k。i指向nums1中最后一个有效元素的位置,j指向nums2中最后一个元素的位置,而k指向合并后nums1数组中最后一个元素应该放置的位置。

逆向合并:从后往前比较nums1和nums2中的元素,将较大的元素放到nums1的k位置上,并相应地移动i、j和k指针。这个过程会一直持续,直到i或j中的一个变为-1,也就是说,nums1或nums2中的元素已经合并完毕。

处理剩余元素:如果nums2中还有剩余元素(这意味着nums1中的元素已经完全处理完毕,而nums2中还有元素未被合并),则将nums2中剩余的元素直接复制到nums1的前面。注意,如果nums1中的元素先处理完,那么nums2中剩余的这部分元素必然都是比nums1中已处理的元素小的元素,因此可以直接复制到nums1的前面。

这种从后往前的合并方法是非常高效的,因为它避免了在合并过程中移动nums1中的元素,从而减少了不必要的操作。

三、解析

这段代码定义了一个名为`Solution`的类,并且包含一个名为`merge`的方法。这个方法接受四个参数:`nums1`、`m`、`nums2`和`n`。

- `nums1`和`nums2`是两个整数列表,分别表示要合并的第一个列表和第二个列表。
- `m`和`n`分别是这两个列表的长度。

在`merge`方法内部,首先使用切片操作符`[:]`将`nums1`和`nums2`的前部分(即长度为`m`和`n`的部分)复制到新的列表中,然后将这两个新列表连接起来形成一个新的列表`nums3`。

最后,使用Python内置的`sorted`函数对`nums3`进行排序,并将排序后的结果赋值给`nums1`。这样就实现了将`nums1`和`nums2`合并并排序的功能。

请注意,这里并没有返回任何值,因为这是一个“副作用”函数,它的作用是直接修改了输入的列表,而不是返回一个新的列表。


1、知识点

1)nums1: List[int]    ---名字是nums1的List(列表)类型的数据,列表里面都是int整数

2)m: int    ----名字是m的int整数类型的数据

3)nums1[:] = nums1[0:m]     ---[:]是切片操作符,表示nums1[:]是nums1列表从0到m长度的列表切片

4) def merge(self, xxx) -> None:   ---表示这个函数没有返回值,或者说是返回值是none

5)sort()函数:是操作list列表的函数

2、解题的关键点

1)最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。

说明:需要把修改数据后的nums1给返回,而不是返回一个新的数组,本次操作需要修改的是nums1

2)

3、衍生知识点

1)python的列表和数组

在Python中,数组和列表(list)并不是完全相同的概念。虽然它们都可以用来存储一系列有序的数据,但它们之间还是有一些区别的。

- 列表(list)是Python内置的一种数据结构,它可以包含任意类型的元素,并且支持动态增长(即可以随时添加或删除元素)。列表使用方括号`[]`来定义,元素之间用逗号`,`分隔。

例如:
```python
my_list = [1, 'hello', 3.14]
```

- 数组(array)则是另一种数据结构,它通常用于存储同一种类型的数据,并且支持高效的随机访问。Python标准库并没有提供直接支持数组的模块,但是可以通过第三方库如`numpy`来创建和操作数组。

例如:
```python
import numpy as np

my_array = np.array([1, 2, 3])
```

总的来说,如果你需要处理不同类型的数据或者需要动态增长,那么应该使用列表;而如果你需要处理大量同类型的数据,并且希望访问速度更快,那么应该考虑使用数组。

2)sort()函数

在Python中,`sort()`函数是列表(list)对象的一个内置方法,用于对列表进行排序。这个函数会直接修改原始列表,而不是返回一个新的排序后的列表。

`sort()`函数的基本语法如下:
```python
list.sort(key=None, reverse=False)
```
其中:

- `key`:可选参数,用于指定一个函数来确定排序顺序。默认情况下,`key`参数为`None`,此时按照元素本身的值进行排序。
- `reverse`:可选参数,用于指定是否要进行降序排序。默认情况下,`reverse`参数为`False`,表示升序排序。

下面是一些示例:

```python
# 对一个整数列表进行升序排序
numbers = [5, 2, 8, 1, 9]
numbers.sort()
print(numbers)  # 输出 [1, 2, 5, 8, 9]

# 对一个字符串列表按照长度进行排序
words = ['apple', 'banana', 'cherry', 'date']
words.sort(key=len)
print(words)  # 输出 ['date', 'apple', 'banana', 'cherry']

# 对一个整数列表进行降序排序
numbers = [5, 2, 8, 1, 9]
numbers.sort(reverse=True)
print(numbers)  # 输出 [9, 8, 5, 2, 1]
```

请注意,`sort()`函数会直接修改原始列表,如果你不想改变原始列表,而是希望得到一个新的排序后的列表,可以使用`sorted()`函数。

3)sort函数和sorted函数的区别

在Python中,`sort` 方法和 `sorted` 函数都用于对序列进行排序,但它们之间存在一些关键的区别:

1. **方法 vs 函数**:
   - `sort` 是列表(list)对象的一个方法,它会就地(in-place)对列表进行排序,也就是说它会修改原来的列表,不会返回任何值(实际上返回 `None`)。
   - `sorted` 是一个内置函数,它可以接受任何可迭代对象(例如列表、元组、字符串等),并返回一个新的、排序后的列表,原来的可迭代对象不会被修改。

2. **返回值**:
   - `sort` 方法没有返回值(或者说返回 `None`),它直接修改原列表。
   - `sorted` 函数会返回一个新的列表,原始输入不变。

3. **通用性**:
   - `sort` 方法只能用于列表。
   - `sorted` 函数可以用于任何可迭代对象。

4. **参数**:
   - 两者都可以接受 `key` 和 `reverse` 参数来自定义排序逻辑。`key` 参数用于指定一个函数,这个函数会被用于序列中每个元素上,然后排序会基于这个函数的返回值进行;`reverse` 参数用于指定排序是升序还是降序。

下面是两者的使用示例:

```python
# 使用 sort 方法
my_list = [3, 1, 4, 1, 5, 9, 2, 6]
my_list.sort()  # 对原列表进行就地排序
print(my_list)  # 输出: [1, 1, 2, 3, 4, 5, 6, 9]

# 使用 sorted 函数
my_tuple = (3, 1, 4, 1, 5, 9, 2, 6)
new_list = sorted(my_tuple)  # 返回一个新的排序后的列表
print(new_list)  # 输出: [1, 1, 2, 3, 4, 5, 6, 9]
print(my_tuple)  # 原元组不变,输出: (3, 1, 4, 1, 5, 9, 2, 6)
```

在选择使用 `sort` 还是 `sorted` 时,你需要考虑是否想要修改原始数据以及你的数据类型是否支持 `sort` 方法。

文章来源地址https://www.toymoban.com/news/detail-861503.html

到了这里,关于【刷爆LeetCode_01题_合并两个有序数组】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode 88 合并两个有序数组

    题目描述: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应

    2024年02月03日
    浏览(18)
  • Leetcode. 88合并两个有序数组

    合并两个有序数组 核心思路: 依次比较,取较小值放入新数组中 i 遍历nums1 , j 遍历nums2 ,取较小值放入nums3中 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 那如果nums[i] 和nums[j]中相等,随便放一个到nums3 此时 nums1 中的元素已经走完了,那么直接把 nums2 中剩下的元素拿到

    2023年04月08日
    浏览(44)
  • LeetCode_88. 合并两个有序数组

    目录 题目描述 思路分析 我的题解 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储

    2023年04月15日
    浏览(18)
  • ​LeetCode解法汇总88. 合并两个有序数组

    https://github.com/September26/java-algorithms 给你两个按  非递减顺序  排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nums1  和  nums2  中的元素数目。 请你  合并   nums2   到  nums1  中,使合并后的数组同样按  非递减顺序  排列。 注意: 最终,合并

    2024年02月12日
    浏览(9)
  • Leetcode每日一题——“合并两个有序数组”

    各位CSDN的uu们你们好呀,又到小雅兰的愉快题解时候啦,今天,我们的题目内容是合并两个有序数组,下面,让我们进入合并两个有序数组的世界吧 示例 1: 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [ 1,2

    2023年04月24日
    浏览(29)
  • LeetCode150道面试经典题-- 合并两个有序链表(简单)

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]    示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3:   输入:l1 = [], l2 = [0] 输出:[0] 递归调用 将这个问题不断拆分

    2024年02月12日
    浏览(10)
  • LeetCode面试算法-力扣 88. 合并两个有序数组

    88. 合并两个有序数组 题目描述     给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意: 最终,合并后数组不应由函数返回,而是存储

    2024年02月10日
    浏览(8)
  • LeetCode-Java:88合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2 ,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况

    2024年02月05日
    浏览(16)
  • 88. 合并两个有序数组、Leetcode的Python实现

    博客主页:🏆李歘歘的博客 🏆 🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点,以及职场小菜鸡的生活。🌺 💗点关注不迷路,总有一些📖知识点📖是你想要的💗 ⛽️今天的内容是     Leetcode  88. 合并两个有序数组        ⛽️💻💻💻

    2024年02月06日
    浏览(14)
  • 【LeetCode】移除元素、删除有序数组中的重复项、合并两个有序数组

    🧑‍💻作者: @情话0.0 📝专栏:《LeetCode》 🔖题目链接:移除元素、删除有序数组中的重复项、合并两个有序数组 给你一个数组 nums 和一个值 val,你需要 原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空

    2023年04月09日
    浏览(14)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包