文章
1
粉丝
407
获赞
2
访问
14.6k
题中所谓“翻煎饼”的方法,就是:将铲子上方的煎饼次序颠倒。
将上述过程模拟为对一个大小为n的数组排序(升序),次数最少就要求:每次将当前数组中尚未排序的最大的数,通过颠倒数组部分元素次序的方法,移至该部分元素的最靠后位置。
以n=5,原始次序为:5、4、2、3、1为例:
第一轮:判断下标为4的元素不是前(4+1)个元素中最大的元素,因此找到最大的元素——5,下标是0,可以直接翻转,得到:1、3、2、4、5。(1次翻转)
第二轮:判断下标为4的元素是前(4+1)个元素中最大的元素,下标为3的元素是前(3+1)个元素中最大的元素,但下标为2的元素不是前(2+1)个元素中最大的元素,因此找到最大的元素——3,下标是1!=0,因此将前(1+1)个元素翻转,得到:3、1、2、4、5,然后再将前(2+1)个元素翻转,得到:2、1、3、4、5。(2次翻转)
第三轮:判断下标为1的元素不是前(1+1)个元素中最大的元素,因此找到最大的元素——2,下标为0,可以直接翻转,得到:1、2、3、4、5。(1次翻转)
因此至少要经过4次翻转。
登录后发布评论
暂无评论,来抢沙发