一道笔试题
有一数组,数组长度n>1,现在让调整数组内元素得位置,满足俩俩相邻元素得绝对值大于等于10(a[i]-a[i-1]>=10, 1<=i<=n-1),如果没有满足条件得排列,返回-1,给出算法和时间复杂度分析。
我用得是穷举排列的方法,直到找出满足条件的一个排列。不知有没有更优的方法,求解这到题目,希望达人赐教!
[解决办法]
此题可转化成图遍历问题。
a[i],a[j]差绝对值>10两点间相连.
则问题转成:能否从某点出发,遍历图。
[解决办法]
就是求哈密顿路径,NPC,没有效率高的算法。