题解 | #牛牛摆放花#
牛牛摆放花
http://www.nowcoder.com/practice/9a11f48530d94188b430db9afe19d20e
题目描述
n朵花排成一圈,最小化相邻两朵花高度差的最大值,输出最大值。
返回按照这些花排成一个圆的序列中最小的“丑陋度”(此句在代码注释中)
题意解析
给你一堆数字让你围成一个圆,计算圆的丑陋度,所谓丑陋度就是这个圆中相邻高度差的最大值。要求你找出所有排列可能最小的那个丑陋度。
示例
输入1:
5,[2,1,1,3,2]
返回值:1
输入2:
3,[30,10,20]
返回值:20
题解
暴力法:全排列
根据题意解析,这个题目其实就是找所有排列组合中,丑陋度最高的一个。
那暴力的办法自然就是进行全排列,然后针对每一种组合计算出其丑陋数,然后取其中最小的。
代码如下:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回按照这些花排成一个圆的序列中最小的“丑陋度” * @param n int整型 花的数量 * @param array int整型一维数组 花的高度数组 * @return int整型 */ // 初始化为Integer.MAX_VALUE,因为花的高度范围是小于MAX_VALUE的,所以设置这个值是合理的 public static int minUgly = Integer.MAX_VALUE; public int arrangeFlowers (int n, int[] array) { perm(array,0,array.length-1); return minUgly; } // 全排列递归写法 public static void perm(int[] array,int start,int end) { if(start==end) { // 此时形成了一种全排列的可能,计算该种排列的丑陋数并与现有最小值比较,取更小的 minUgly = Math.min(minUgly,helper(array)); } else { for (int i = start; i <= end; i++) { swap(array,start,i); // 递归确定start+1位置的数值 perm(array,start+1,end); // 将交换还原 swap(array,start,i); } } } // 交换 i,j位置的数字 public static void swap(int[] array,int i,int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // 计算当前排列下的丑陋度 public static int helper(int[] array) { //初始化为收尾的差的绝对值 int max = Math.abs(array[0]-array[array.length-1]); for(int i=1;i<array.length;i++){ // 丑陋度 = max(高度差) max = Math.max(max,Math.abs(array[i]-array[i-1])); } return max; } }
该解法很明显在题目描述的数据范围下会出现超时情况。
因为该解法的时间复杂度为,因为n个数字的全排列有种可能,空间复杂度为
寻找更优解
首先,我们假设现在不是一个圈,只是一条线,请问这个问题如何解决?
很简单,对这组数进行排序,然后找到其中相邻高度差最大的值就是解。
那现在围成一个圆呢?
围城圆之后由于首尾的差就要被计算了,所以刚刚的方法就不行了。
我发现这个问题不能靠想的,要具体动手去试,才能找到思路。
当只有1个数和2个数的时候,只有一种摆法,我们从3个说起
假设当前有3个,高度从小到大依次是a、b、c,
此时高度差最大肯定是c和a,但是无论哪一种摆法,ca肯定都会相邻,所以此时随便哪种都是一样的结果;
那如果是4个呢?分别高度从小到大依次为 a,b,c,d
我们是有办法避开最大的高度差a和d的。
于是我们现从大到小取出d,(也可以从小到大取),此时剩下的abc要选择2个放到d的旁边,应该取bc,因为a和d的高度差最大,肯定不能连着放。最后剩下a,任意放在一遍都可以,因为这两种情况下的结果是一样的,如下图所示:
继续考虑5个,分别从小到大为 a,b,c,d,e,当确定的最大值e以及最大值两侧c、d后,来到一个选择,可能得答案只有两种,分别如下图所示:
图中上面和下面两种可能得情况中,
由于上面的情况中存在 这个可能得最大值,而这个最大值是肯定大于下面那种情况的(圈红的部分),所以下面的才是最优解。
依次类推:我们发现,如果有n个数的排列,最优解其实是按照顺序分布在两边的,且依次相隔2个位置
所以,n个数的有序数列,其最优解的序列为
按照这个思路写代码,就简单很多了
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回按照这些花排成一个圆的序列中最小的“丑陋度” * @param n int整型 花的数量 * @param array int整型一维数组 花的高度数组 * @return int整型 */ public int arrangeFlowers (int n, int[] array) { Arrays.sort(array); //因为按照我们刚刚的思路,第一和第二小的数肯定是会被分到2边的,所以围成圆的话,其高度差肯定是一个可能的结果,所以以它作为一个初始值是合理的 int ans = array[1] - array[0]; // 依次比较2个身位差之间数字的差值,由于已经排序所以不需要考虑绝对值问题 for(int i = 2 ; i < n ; i++){ ans = Math.max(ans , array[i] - array[i - 2]); } return ans; } }
细心的同学应该会发现,在上面推理的时候会发现挡奇数个数的时候(如上面5个数的时候),可能得结果中其实是存在一种可能是的,但是实际算法中只计算了array[i] - array[i - 2]
相邻两个身位的数值差,会不会有问题呢? 其实这样是没问题的,因为在奇数个的时候其答案中既存在也存在,由于有序性,所以是肯定要大于的,而丑陋数是差的最大值,所以在这种情况下不可能是丑陋数,所以不需要考虑。
该解法的时间复杂度为 ,因为其中有排序操作
空间复杂度为