C/C++教程

小C秋招面试算法题:合并k个有序数组、合并k个有序链表(分治思想)

本文主要是介绍小C秋招面试算法题:合并k个有序数组、合并k个有序链表(分治思想),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这里写目录标题

  • 写在前面
  • 一、合并k个有序数组
    • 1、合并两个有序数组
    • 2、合并k个有序数组
    • 3、分治实现合并k个有序数组
  • 二、合并k个有序链表
    • 1、合并两个有序链表
    • 2、合并k个有序链表
  • 后语

写在前面

目前大部分公司的秋招都已经结束,博主小C也在昨天10.31结束了秋招最后一场面试。最近2个月的时间,做的事情大概就是投简历、刷题、笔试、复习八股文、面试,11月到来了,新的一个月开始,忽然感觉一切都是新的,可以放松一下近两月的紧绷状态,做一些自己的事情了,当然也要开始完成毕业论文啦。

参加的所有面试,结束之后都进行了复盘记录,以后有时间整理出来,写写这一段面试经历,分享面经。博主小C就读于双非一本大学,Java后端选手,这一段时间过来,感触还是很多~ ,其实自己并不是大佬级别的,只是勤勤恳恳,不算差而已。

今天先记录一下面试中经常考察的两个算法题,主要为了总结以作备忘,算法思想还是很重要的,也希望能帮助到有需要的朋友。

高频出现在面试中的考察的题目:合并k个有序数组合并k个有序链表

一、合并k个有序数组

看到这道题目,可以先联想到合并两个有序数组。所以,k个就可以比作很多个合并,每次合并两个数组。

1、合并两个有序数组

那先来看看合并两个有序数组怎么写。

public static int[] mergeTwoArray(int[] a1, int[] a2) {
    int m = a1.length, n = a2.length;
    int[] temp = new int[m + n];
    int i = 0, j = 0, idx = 0;
    while (i < m || j < n) {
        if (i == m) {//a1遍历完
            temp[idx++] = a2[j++];
        } else if (j == n) {
            temp[idx++] = a1[i++];
        } else if (a1[i] >= a2[j]) {
            temp[idx++] = a2[j++];
        } else if (a1[i] < a2[j]) {
            temp[idx++] = a1[i++];
        }
    }
    return temp;
}

看看代码,是不是感觉还行,思路很直接:创建一个新数组,来存放合并结果,每次就比较一下a1a2的每个元素,小的就先加到结果数组中,比较到一个数组末尾后,如果另一个还有元素,直接加上temp数组就OK了。

2、合并k个有序数组

合并两个有序数组可以如此操作,那合并k个该怎么操作?

实际上,按合并两个的思路,我们可以先拿两个出来合并,合并后的新数组再跟后面的数组进行合并,试试看!

/**
 * 从前往后每两个数组合并
*/
public static int[] sort(int[][] a) {
    int row = a.length, col = a[0].length;
    int i;
    int[] last = a[0];
    for (i = 1; i < row; i++) {
        last = mergeTwoArray(last, a[i]);
    }
    return last;
}

为了方便,我使用一个二维数组保存这k个有序数组,每一行就代表一个有序数组,就像以下这样存储。

int[][] a ={{1, 3, 3, 5, 10},
            {3, 5, 7, 15, 18},
            {2, 15, 17, 18, 20}};

写一个main方法,测试一下

public static void main(String[] args) {
    int[][] a =
    {{1, 3, 3, 5, 10},
     {3, 5, 7, 15, 18},
     {2, 15, 17, 18, 20}};
    int[] result = sort(a);
    for (int num : result)
        System.out.print(num + " ");
}

合并结果:1 2 3 3 3 5 5 7 10 15 15 17 18 18 20

到这里算是一种可以的解法了,但分析一下时间复杂度sort()方法O(n),mergeTwoArray方法O(n),双重嵌套就是O(n2)。

3、分治实现合并k个有序数组

所以看看有什么优化的方法,每个合并都是一个子问题,一时就想到分治算法,分为前后半段合并,然后细分也是如此。写一个merge方法。

public static int[] merge(int[][] a, int left, int right) {
    if (left == right)
        return a[left];
    if (left > right)
        return new int[0];

    int mid = (right - left) / 2 + left;
    int[] leftArray = merge(a, left, mid);
    int[] rightArray = merge(a, mid + 1, right);

    return mergeTwoArray(leftArray, rightArray);
}

leftright的意思就是:每次合并分为left~mid、mid + 1~right的数组,就是分治的思想,对左半段和右半段分别处理,然后再进行归并。

public static void main(String[] args) {
    int[][] a =
    {{1, 3, 3, 5, 10},
     {3, 5, 7, 15, 18},
     {2, 15, 17, 18, 20}};
    int[] result = merge(a, 0, a.length - 1);
    for (int num : result)
        System.out.print(num + " ");
}

合并结果:1 2 3 3 3 5 5 7 10 15 15 17 18 18 20

二、合并k个有序链表

这个题目的思想类似上面合并数组,只是以链表的形式呈现。

首先同样看看如何合并两个有序链表,LeetCode21 合并两个有序链表这个题目是完全一样的,可以练练。

链表结点的结构是这样的:

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; 
     }
}

1、合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null && l2 == null)
        return l1;
    else if(l1 == null)
        return l2;
    else if(l2==null)
        return l1;

    ListNode head = new ListNode(0);
    ListNode pre = head;//辅助指针保存当前比较的位置,准备下个next

    while(l1 != null && l2 != null){
        if(l1.val <= l2.val){
            pre.next = l1;
            l1 = l1.next;
        }
        else{
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;//经过一次比较之后,更新位置,指向下一个
    }
    if(l1 != null)
        pre.next = l1;
    else
        pre.next = l2;

    return head.next;
}

对于链表的操作,一般就是修改指针的指向,并使用辅助结点进行实现。上面程序的结构可以对于合并两个有序数组,理解起来更容易。

合并两个有序链表这道题在LeetCode上标记是简单,而合并k个有序数组标记了困难,可见还是有一定的难度。

不过,完全不用慌,也许你理解了合并两个有序链表之后,这道题实际采用上面的分治思想或者每次合并两个的方案,都是比较简单的事情了,只需要在添加一个方法。

2、合并k个有序链表

往简单想,真的不难,来看看~

同样保留合并两个有序链表mergeTwoLists方法,只需再增加一个merge方法,就搞定!

public ListNode merge(ListNode[] lists, int l, int r) {//分治,归并
    if (l == r) {
        return lists[l];
    }

    if (l > r) {
        return null;
    }

    int mid = (l + r) >> 1;//中点

    ListNode node1 = merge(lists, l, mid);//左半段归并排序
    ListNode node2 = merge(lists, mid + 1, r);//右半段归并排序
    return mergeTwoLists(node1, node2);//合并两段
}

然后在主方法直接调用merge就完成了。

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = null;
    ans = merge(lists,0,lists.length - 1);
    return ans;
}

后语

这篇记录的是面试中常见的算法考察题目,由浅入深,更好理解,有时候一个算法思想可以融会贯通,这个过程就需要千锤百炼了,以后还需要更进一步学习。

今天,11月1号,是我秋招结束的第一天,在此记录。以后还会把我的面试经历分享给大家,希望大家一起成长,收获满满~



如果觉得不错欢迎“一键三连”哦,点赞收藏关注,评论提问建议,欢迎交流学习!一起加油进步,我们下篇见!


本篇内容首发我的CSDN博客:https://csdn-czh.blog.csdn.net/article/details/120883869

这篇关于小C秋招面试算法题:合并k个有序数组、合并k个有序链表(分治思想)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!