程序员面试题精选100题(41)-把数组排成最小的数(算法)

面试题 时间:2019-09-22 手机网站
A1A2…AyAxAx+1…Ay-2Ay-1…An<A1A2…AyAx+1Ax…Ay-2Ay-1…An<…< A1A2…AyAx+1Ax+2…Ay-2Ay-1Ax…An

所以A1A2…Ax…Ay…An< A1A2…Ay…Ax…An。这和我们的假设的A1A2…Ay…Ax…An <A1A2…Ax…Ay…An相矛盾。

所以假设不成立,我们的算法是正确的。