LeetCode题解-合并K个有序数组-Java

简介: 合并K个有序数组-Java

利用21题合并两个有序数组的代码,使用for循环进行合并,效率较低;参照第一名的代码,使用分治,改变对数组的处理方法,可以大幅度提高处理效率:

修改后:

public ListNode mergeKLists(ListNode[] lists) {
   
        if(lists==null||lists.length==0)return null;
        return sort(lists, 0, lists.length-1);
    }
public static ListNode sort(ListNode[] lists ,int low , int high) {
   
        if(low>=high) return lists[low];
        int mid = (high - low )/2 + low;
        ListNode l1 = sort(lists ,low , mid);
        ListNode l2 = sort(lists , mid +1 ,high);
        return mergeTwoLists(l1, l2);
}

原:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   
    public ListNode mergeKLists(ListNode[] lists) {
   
        int length = lists.length;
        if(length==0)return null;
        if(length==1)return lists[0];
        ListNode result = lists[0];
        for(int i = 1 ;i < length; i++) {
   
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }
    //重复节点值
    //default关键字修饰变量,在不同包时无法访问
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   
        ListNode result = new ListNode(0);
        ListNode point = result;
        //{5,1 2 4}
        while(l1!=null&&l2!=null) {
   
                if(l1.val>l2.val) {
   
                    point.next = new ListNode(l2.val);
                    point = point.next;
                    if(l2.next==null||l2.next.val>l1.val) {
   
                        point.next = new ListNode(l1.val);
                        point=point.next;
                        l1=l1.next;
                    }
                    l2=l2.next;
                }else if(l1.val<l2.val){
   
                    point.next = new ListNode(l1.val);
                    point = point.next;
                    if(l1.next==null||l1.next.val>l2.val) {
   
                        point.next = new ListNode(l2.val);
                        point=point.next;
                        l2=l2.next;
                    }
                    l1=l1.next;
                }else {
   
                    point.next = new ListNode(l2.val);
                    point=point.next;
                    point.next = new ListNode(l2.val);
                    point=point.next;
                    l1=l1.next;
                    l2=l2.next;
                }
        }
        while(l1!=null) {
   
            point.next = new ListNode(l1.val);
            point = point.next;
            l1=l1.next;
        }
        while(l2!=null) {
   
            point.next = new ListNode(l2.val);
            point = point.next;
            l2=l2.next;
        }
        return result.next;
    }

}
目录
相关文章
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
|
1月前
|
算法
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
23 1
|
5天前
|
算法 Java C语言
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
|
1月前
|
存储
【合并两个有序数组】LeetCode第88题讲解
【合并两个有序数组】LeetCode第88题讲解
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
[Java·算法·简单] LeetCode 13. 罗马数字转整数 详细解读
22 0
|
25天前
|
Java
java实现向有序数组中插入一个元素
java实现向有序数组中插入一个元素
8 0
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode15. 三数之和
[Java·算法·中等] LeetCode15. 三数之和
29 0
|
1月前
LeetCode刷题---80. 删除有序数组中的重复项 II(双指针)
LeetCode刷题---80. 删除有序数组中的重复项 II(双指针)
|
1月前
LeetCode刷题---26. 删除有序数组中的重复项(双指针)
LeetCode刷题---26. 删除有序数组中的重复项(双指针)