有序数组循环后如何复原为有序

有序数组A如{1,2,3,4,5,6},循环后,变为B:{3,4,5,6,1,2},假定我们并不知道partition point,也就是不知道循环后原来的数组首元素如1在循环后数组B中的位置,那么如何复原为原始有序数组A:{1,2,3,4,5,6}呢?

算法分两步

  • 使用partition_point找到partition point,partition point前的元素都大于等于B的首元素。比如B数组为{3,4,5,6,1,2}前四个元素都大于等于B的首元素3,那么partition point指向第五个元素1。
  • 对数组B循环,将partition point指向的元素作为循环后结果数组的首元素。结果数组和A完全相等。

实现如下:

  #include <ranges>
  #include <algorithm>
  #include <iostream>
  #include <functional>
  #include <ranges>
  int main(){
    int a[]= {3,4,5,6,1,2};
    auto pos=std::ranges::partition_point(a, std::bind_front(std::less_equal{},a[0]));
    std::ranges::rotate(std::ranges::begin(a),pos,std::ranges::end(a));
    std::ostream_iterator<int> oit(std::cout, ",");
    std::ranges::copy(a, oit);
  }
Posted 2023-05-03