LeetCode 969. 煎饼排序

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 969. 煎饼排序

思路分析

解题思路：

遍历数组元素，从大到小，即从 n 到 1，其中 n 为数组长度。

对于当前元素 x，找到数组中前 x 个元素中的最大值的位置 maxIndex。

如果 maxIndex 不等于 x-1，则执行两次煎饼翻转：

第一次：将 maxIndex+1 位置的元素反转到数组的开头，这样最大元素移到数组的开头位置。

第二次：将 x-1 位置的元素反转到数组的开头，将最大元素移到正确的位置。

重复这个过程，逐步将所有元素排序，直到整个数组有序。

参考代码

func pancakeSort(nums []int) []int {
	n := len(nums)
	var res []int

	for x := n; x > 0; x-- {
		maxIndex := findMaxIndex(nums[:x])

		if maxIndex != x-1 {
			reverse(nums, maxIndex)
			res = append(res, maxIndex+1)
			reverse(nums, x-1)
			res = append(res, x)
		}
	}

	return res
}

func findMaxIndex(nums []int) int {
	maxIndex := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[maxIndex] {
			maxIndex = i
		}
	}
	return maxIndex
}

func reverse(nums []int, k int) {
	left, right := 0, k
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/05273466