C++程序 计算生成排序数组所需旋转的次数
给定一个 数组 arr[] ,任务是找到将给定数组转换为排序形式所需的旋转次数。
示例:
输入: arr[] = {4, 5, 1, 2, 3}
输出: 2
解释:
需要2次逆时针旋转后形成排序数组{1, 2, 3, 4, 5}。
输入: arr[] = {2, 1, 2, 2, 2}
输出: 1
解释:
需要1次逆时针旋转后形成排序数组{1, 2, 2, 2, 2}。
Naive Approach:
为了解决上述问题,我们首先观察到,如果数组中有 n 个元素,则排序后最大的元素位于第(n – 1)个位置。进行k次逆时针旋转后,最大元素将位于索引(k – 1)(从开始数的第k个元素)。另外一个需要注意的是,旋转后最大元素的下一个元素始终是最小元素(除非最大元素在最后一个索引上,如果没有旋转就可能出现)。
因此,
旋转次数(k) = 数组中最小元素的索引(k)
下面是实现上述方法的代码:
输出:
时间复杂度: O(N)
辅助空间: O(1)
Efficient Approach:
为了优化上述方法,我们将使用二分查找。我们可以注意到,在排序并旋转后,给定的数组被分成两个具有非递减元素的部分,这是二分查找的唯一前提条件。在数组中执行递归二分查找以找到最小元素的索引。
下面是实现上述方法的代码:
输出:
时间复杂度: O(N)
对于没有重复项的数组,复杂性将为O(logN)。但是,如果数组包含重复项,则它将递归地调用搜索来寻找两个半部分。因此,最坏情况下的复杂度将是O(N)。
辅助空间: O(N)
在最坏的情况下,递归调用堆栈将同时具有N / 2个递归调用。