精华内容
下载资源
问答
  • 合并两个有序数组 题目来源: leetcode-88题 来源: 公众号:五分钟学算法 思路: 我们已知m和n,就可以知道合并后数组的总长度。 算法关键:双指针+从后向前比较 具体思路: 设置双指针分别指向有序数组的最后一...

    合并两个有序数组

    题目来源: leetcode-88题
    在这里插入图片描述

    来源: 公众号:五分钟学算法

    思路:

    1. 我们已知m和n,就可以知道合并后数组的总长度。
    2. 算法关键:双指针+从后向前比较

    具体思路:

    1. 设置双指针分别指向有序数组的最后一位。
    2. 循环终止条件:其中一个指针不再指向数组。
    3. 开始循环:从后向前比较双指针指向的值,大的或相同的值放在num1空间(合并后的空间)的尾部。
    4. 循环结束后检查指针:如果指向num2的指针还有效,说明num2中存在比num1最小值还小的元素,将这个元素直接放到num1之前即可。

    c++实现:

    class Solution {
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int len=m+n;
            while(m>0&&n>0){
                if(nums2[n-1]>=nums1[m-1]){
                    nums1[--len]=nums2[--n];
                }
                else nums1[--len]=nums1[--m];
            }
            //最后num2还有值。说明剩下的值比nums1最小值都小。直接copy进入nums1中即可。
            while(n>0){
                nums1[--len]=nums2[--n];
            }
        }
    };
    

    合并两个有序链表

    题目来源:leetcode21题。
    在这里插入图片描述
    解题思路:
    可以用递归,也可以用迭代。

    迭代

    我们设置两个指针指向两个链表,同时设定一个头结点和一个跟踪结点,头结点用于返回结果链表,跟踪结点用于插入。
    具体思路:

    1. 循环终止条件:其中一个链表的结点为空。
    2. 循环开始,依次比较两个链表的结点大小,使跟踪结点始终指向小的结点.
    3. 循环结束,判断不为空的链表,直接使跟踪节点指向该不为空的链表即完成了排序。
      代码
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* re=new ListNode(-1);
            ListNode *p=re;//记录了整个链表的第一个。
            while(l1!=NULL && l2!=NULL){
                if(l1->val<=l2->val){
                    re->next=l1;
                    re=re->next;
                    l1=l1->next;
                }
                else {
                    re->next=l2;
                    re=re->next;
                    l2=l2->next;
                }
            }
            if(l1!=NULL){
                re->next=l1;
            }
            else re->next=l2;
            return p->next;
        }
    };
    

    递归

    在这里插入图片描述
    代码:(来源自Leetcode)

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (l1 == nullptr) {
                return l2;
            } else if (l2 == nullptr) {
                return l1;
            } else if (l1->val < l2->val) {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            } else {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }
    };
    
    
    展开全文
  • public static void main(String[] args) { int[] a=new int[]{1,6,9,122}; int[] b=new int[]{2,3,4}; int[] temp=new int[7]; int[]d= compareDG(a,0,b,0,temp,0); fo...
     public static void main(String[] args) {
            int[] a=new int[]{1,6,9,122};
            int[] b=new int[]{2,3,4};
            int[] temp=new int[7];
    
    
           int[]d= compareDG(a,0,b,0,temp,0);
            for (int i=0;i<7;i++){
                System.out.println(d[i]);
            }
        }
    
    
        private static int[] compareDG(int[] a,int i, int[] b,int j,int[] c,int k) {
            if (i+j==c.length){
                return c;
            }else if (a.length==i){
                c[k++]=b[j++];
            }else if (b.length==j){
                c[k++]=a[i++];
            }else {
                if (a[i]<b[j]){
                    c[k++]=a[i++];
                }else {
                    c[k++]=b[j++];
                }
            }
            return compareDG(a,i,b,j,c,k);
        }
    }

     

    展开全文
  • 再去执行merge(arr, lo, mid, hi),然后进行两个元素的比较,排序。 我感觉我这样的理解显然是错误的,我一直弄不懂一个递归函数的下面的执行语句究竟是怎么执行的。比如我假设有一个全局变量i放到了第一个...
  • 21 合并两个有序链表 题目描述 题目链接 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3...

    21 合并两个有序链表

    题目描述

    题目链接
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    示例:
    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4

    方法一 递归

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null)
                return l2;
            else if(l2 == null)
                return l1;
            else if(l1.val < l2.val){
                l1.next =  mergeTwoLists(l1.next, l2);
                return l1;
            }
            else{
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
    

    方法二 迭代

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null)
                return l2;
            if(l2 == null)
                return l1;
            ListNode preNode = new ListNode(-1);
            ListNode prev = preNode;
            while(l1!=null && l2!=null){
                if(l1.val < l2.val){
                    prev.next = l1;
                    l1 = l1.next;
                }
                else{
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
            //有一个链表还没合并完
            prev.next = (l1 == null) ? l2 : l1;
            return preNode.next; 
        }
    }
    

    88 合并两个有序数组

    题目描述

    题目链接
    给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

    说明:

    初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
    你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

    示例:

    输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6], n = 3

    输出: [1,2,2,3,5,6]

    方法一 合并后排序

    System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。其函数原型是:

    public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);
    * @param      src      the source array. 源数组
    * @param      srcPos   starting position in the source array. 源数组的起始位置
    * @param      dest     the destination array. 目标数组
    * @param      destPos  starting position in the destination data. 目标数组的起始位置
    * @param      length   the number of array elements to be copied. 复制的长度
    
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            System.arraycopy(nums2, 0, nums1, m, n);
            Arrays.sort(nums1);
        }
    }
    

    时间复杂度为O((m+n)log(m+n))O((m+n)log(m+n))
    空间复杂度为O(1)O(1)

    方法二 双指针

    从后往前依次将nums2中的元素添加到nums1中。

    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int k = m + n - 1;//从后往前插入,记录当前插入位置
            int p1 = m -1;//nums1当前比较位置
            int p2 = n -1;//nums2当前比较位置
            while(p2 >= 0){//将nums2插入到nums1
                nums1[k--] = (p1>=0 && nums1[p1]>=nums2[p2]) ? nums1[p1--] : nums2[p2--];
            }
        }
    }
    

    时间复杂度

    • 最优的情况下是nums1中的值都小于nums2中得值,执行n次,时间复杂度为O(n)O(n)
    • 最坏的情况是,nums2的n个元素需要插入到nums1之前,nums1的m个元素需要后移,时间复杂度为O(m+n)O(m+n)
    • 因此时间复杂度为O(m+n)O(m+n)

    空间复杂度
    O(1)O(1)

    展开全文
  • if not l1: return l2 # 终止条件,直到两个链表都空 if not l2: return l1 if l1.val <= l2.val: # 递归调用 l1.next = self.mergeTwoLists(l1.next,l2) return l1 else: l2.next = self.mergeTwoL

    class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    if not l1: return l2 # 终止条件,直到两个链表都空
    if not l2: return l1
    if l1.val <= l2.val: # 递归调用
    l1.next = self.mergeTwoLists(l1.next,l2)
    return l1
    else:
    l2.next = self.mergeTwoLists(l1,l2.next)
    return l2

    给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

    说明:

    初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
    你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

    示例:
    输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6], n = 3
    输出:[1,2,2,3,5,6]

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/merge-sorted-array
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    “”"
    Do not return anything, modify nums1 in-place instead.
    “”"
    if m == 0:
    for i in range(n):
    nums1[i] = nums2[i]
    for x in nums2:
    for i in range(m):
    if x < nums1[i]:
    nums1.insert(i,x)
    nums1.pop()
    m = m + 1
    break
    if x >= nums1[m-1]:
    nums1.insert(m,x)
    nums1.pop()
    m = m + 1
    break
    两指针

    class Solution(object):
    def merge(self, nums1, m, nums2, n):
    “”"
    :type nums1: List[int]
    :type m: int
    :type nums2: List[int]
    :type n: int
    :rtype: void Do not return anything, modify nums1 in-place instead.
    “”"
    # two get pointers for nums1 and nums2
    p1 = m - 1
    p2 = n - 1
    # set pointer for nums1
    p = m + n - 1

        # while there are still elements to compare
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] =  nums1[p1]
                p1 -= 1
            p -= 1
        
        # add missing elements from nums2
        nums1[:p2 + 1] = nums2[:p2 + 1]
    																三指针
    
    展开全文
  • 21. 合并两个有序链表 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 方法一: 递归 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; }...
  • 链表可以选用迭代或递归方式完成反转。你能否用种方法解决这道题? 示例1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例2: 输入:head = [1,2] 输出:[2,1] 示例 3: 输入:head = [] 输出:[] 2、提示 ...
  • 数据结构中树的简单操作,一开始想着用循环做,后来觉得不行,就用递归写了。慢慢的开始理解了递归的思想。 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x...
  • 归并算法采取思想是分治思想,分治思想简单说就是分而治之,将一大问题分解为小问题,将小问题解答后合并为大问题的答案。乍一看跟递归思想很像,确实如此,分治思想一般就是使用递归来实现的。但是需要注意的是:...
  • 寻找两个有序数组中的第k个数 假设有两个数组A与B A为[1,2,5,6.7] B为[1,2,3,4,5] 现在需要寻找A、B合并之后的数组中的第4个数 方法一 比较偷懒的方法 直接使用C++中的merge函数将A与B合并为一个有序数组再按照顺序...
  • 从零开始的力扣(第三十三天)~ 1. 验证二叉搜索树 给定一二叉树,判断其是否是一有效的二叉搜索树。 假设一二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。...最开始想法是递归左子树与右子...
  • 思路:每次比较两个数组的第一个数,取较小的那一个,取完之后将该数从对应数组中删除,然后继续比较,如果某一数组为空,则直接将另外一个数组的元素依次复制到新的合并数组中即可。 #include &lt;iostream&...
  • Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归  (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组...
  • 计算两个有序数组的中位数

    千次阅读 2018-09-04 11:56:01
    请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))    类比一个数组的中位数,求两个数组的中位数就相当于把两个数组合并后的一个数组的中位数,例 输入: num1=[1,3,5] num2=[2,4,6] ...
  • 题给了俩有序数组,要求合并后的中位数,要求用lg(m+n)的算法,明显是要二分了,但是正着写太麻烦了,还要考虑奇偶,于是我参考了一下网上大多数人的做法,用递归的方式求。 我用C++写完交了后告诉我才击败了6%...
  • 21.合并两个有序链表 问题描述:将两个升序链表合并成一个新的升序链表并返回 思路: 链表知识点掌握得还行,而且如果熟悉归并排序的话这种题就手到擒来,要么迭代要么递归实现。 链表定义 /** * Definition for ...
  • 分别比较两个链表大小,然后用归并的思想连接这些点即可 时间复杂度是O(n+m)O(n + m)O(n+m),空间复杂度是O(1)O(1)O(1) 代码 非递归写法 /** * Definition for singly-linked list. * struct ListNode { * int ...
  • 对于一规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原...
  • 合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4(1)非...
  • 找出a,b(合并为一大的有序数组后)的中位数(或下中位数)。要求时间复杂度为o(log(m+n)). 分析 :对于数组a,若a的长度m为奇数,则a[(m-1)/2]即为中位数;若m为偶数,则a[(m-1)/2]为下中位数;可知若一数为中位...
  • # Leetcode 合并两个有序链表 # 非递归方法 # 我使用了较为笨的一种方法来接 先提取所有数到数组--->排序--->有了顺序表转换为链表就方便了 # 考虑到链表的特殊性质,我把他们一个个先实例化为一个个仅仅含有...
  • 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的...tips: 与合并两个有序数组思路一致,可以用迭代与递归两种方法。 递归代码如下: class Solution: def mergeT...
  • python练习(leetcode)–合并两个有序链表 一.题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 自我理解是怎样的合并法,先把两个数组分成A,B两组再看...
  • 这个题目就是归并排序中的归并操作,将两个有序数组(链表)合并为一个有序的数组。 非递归: 第一个while循环,将 l1 和 l2 进行比较,谁小谁就合并到 listNode,直到 l1 或者 l2 为空 第二个while循环和第三...
  • 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。...非递归法较为简单,与合并两个有序数组类似  /** * Definition for singly-linked list. * ...
  • 前面写过合并两个数组,然后采用归并排序对某个数组进行了排序。...先来合并两个有序链表 #include<iostream> //首先定义一个链表 struct ListNode{ int data; ListNode* next; }; ListNode* mergeTwo...
  • 合并K已排序数组(Python)

    千次阅读 2018-09-03 12:08:38
    将K个已排序数组合并成一个数组,如merge([[2,4,5],[1,3,9],[6,7,8]]) = [1,2,3,4,5,6,7,8,9] 代码思路: 本题采用归并算法较为简单清晰。...然后再将她们按照两个有序数组的样子合并起来。这样说起来可能...
  • 什么是合并两个有序链表 假设有两条链表,这两条链表分别都是升序排列的,如下图所示: 现在要求将二者合并成一条链表,并且该链表也是升序排列的,合并后的链表如下图所示: 思路 如果对归并排序有所了解,那么这...
  • step1:默认数组A长度小于数组B的长度,合并之后的有序数组记作数组A+B,他的中位数在位置k step2:由于数组AB都是有序数组,所以数组AB的中位数是A[k/2]和B[k/2]; step3:以k/2为界限将数组AB分别分割成数组A1A2和数...
  • * 传入两个有序数组a和b,返回一个排好序的合并数组 * */ public static int[] sort(int[] a, int[] b){ int[] c = new int[a.length + b.length]; //定义元素下标 int aNum = 0, bNum = 0, cNum = 0;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 820
精华内容 328
关键字:

递归合并两个有序数组