今日面试题:一个都不能少

有k个有序的数组,请找到一个最小的数字范围。使得这k个有序数组中,每个数组都至少有一个数字在该范围中。

例如:

1: 4, 10, 15, 24, 26
2: 0, 9, 12, 20
3: 5, 18, 22, 30

所得最小范围为[20,24],其中,20在2中,22在3中,24在1中。

相差甚远面试题分析

原题

给定一个数组,我们可以找到两个不相交的、并且是连续的子数组A和B,A中的数字和为sum(A), B中的元素和为sum(B)。找到这样的A和B,满足sum(A) - sum(B)的绝对值是最大的。 例如:[2, -1 -2, 1, -4, 2, 8]划分为A=[-1, -2, 1, -4], B=[2, 8], 最大的值为16

分析

如果没有比较丰富的经验,这个题目咋一看,有一种不明觉厉的感觉。但只要逐层分析,就可以看到,其实只要分析两层就可以了。首先我们来看看题目有哪些要点(明确题意,有不清楚的,一定要澄清。):

  1. 子数组是不相交的

  2. 子数组是连续的,这个有点多余,但还是强调一下得好

然后题目的要求是,差的绝对值最大。那我们自然而然能够想到:找到的两个不相交的子数组,一个值要很小,一个值要很大。这样才能够保证差的绝对值最大。那如何找到这样的数组呢?我们从不相交的这个条件入手。看题目中例子(从简单的例子出发,发现解决方案,是面试中常用技巧。切记!):

0    1    2    3    4    5    6
2    -1    -2    1    4    2    8

看上面的表格,如果两个子数组不想交,我们有六个位置,作为划分的备选,0和1之间、1和2之间、2和3之间,...,直到5和6之间。这六个位置,都可以将数组划分为两部分。我们设定,数组长度为n,i将数据划分为两部分分别为 [0,i-1]和[i,n-1]。都是两边包含的集合。i是从1到n-1的。

对于任意的i,我们得到了两部分[0, i-1]和[i, n-1]。接下来,就是在这两部分中,找到一个和最小的子数组A,以及和最大的子数组B。那么A-B的绝对值,就是i这个划分下,满足条件的两个数组的差的最大值。对于,所有的i而言,这个绝对值最大时的A和B就是我们要找到的。

思路通顺了,接下来要确定,找到在i处划分,和最大以及和最小的子数组的方法。这里,就要使用到,我们前几天分享的动态规划的思想。那篇文章,大家好好阅读分析了么。相信一定能够给大家带来很多的启发。回到这个题目,我们单独的考虑,给定一个数组,求和最大的子数组以及和最小的子数组。

先分析和最大的子数组,这个问题,是比较经典的问题了,但是我们这里要处理的是,求得每一个i左侧的最大连续子数组。作如下分析,假设数组为X, 假设max_until[i]表示,以i位置结尾的连续子数组的最大和。max_until[i]和max_until[i-1]是什么关系呢?

  1. 如果X[i] + max_until[i - 1] > max_until[i - 1] and X[i] + max_until[i- 1] > X[i]。那么X[i]应该加入到连续子数组中,max_until[i] = max_until[i-1] + X[i].

  2. 否则max_until[i] = X[i],连续子数组只有一个元素。

但是,我们要的并不是以i结尾的子数组,尽管给的例子中是这样的,我们要的是i之前的所有连续子数组中,和最大的。并不一定包括i。要如何处理呢?我们再开辟子数组max_left[i]表示[0,i]中连续子数组的最大值。那这个值要如何求得呢?我们在遍历数组,求得max_until[i]的时候,max_left[i]只需要在max_until[i]和此前保存的最大值里取最大的即可。也就是一次遍历,就可以完全求得max_until数组和max_left数组。同理可以求得min_until以及min_left数组。

这是处理的划分的左半部分。那么右半部分呢?

右半部分的思路也是一样的,只不过,我们在遍历数组的时候,需要从右向左进行遍历。

总结整个方法的流程如下:

  1. 从左向右遍历数组,计算max_left和min_left数组,O(n)时间复杂度

  2. 从右向左遍历数组,计算max_right和min_right数组,O(n)时间复杂度

  3. 然后对于每一个i,i从1开始到n-1,计算max_left[i - 1] - min_right[i], max_right[i] - min_left[i - 1]。选取绝对值最大的。

方法的整体空间复杂度为O(n),时间复杂度也是O(n)。

总结

这个题目,其实是采用动态规划解决最大连续子数组和问题的变种,又多了一层思考。面试者在遇到一个新的题目的时候,不要慌乱,对问题进行仔细分析,进而对其进行分解,分解为自己熟悉的问题。那问题也就解决了。

本文来自微信:待字闺中,2013-07-16发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。