数据结构----翻转数组

题目描述

给定一个长度为n的整数数组a，元素均不相同，问数组是否存在这样一个片段，只将该片段翻转就可以使整个数组升序排列。其中数组片段[l,r]表示序列a[l], a[l+1], ..., a[r]。原始数组为

a[1], a[2], ..., a[l-2], a[l-1], a[l], a[l+1], ..., a[r-1], a[r], a[r+1], a[r+2], ..., a[n-1], a[n]，

将片段[l,r]反序后的数组是

a[1], a[2], ..., a[l-2], a[l-1], a[r], a[r-1], ..., a[l+1], a[l], a[r+1], a[r+2], ..., a[n-1], a[n]。

输入第一行数据是一个整数：n (1≤n≤10⁵)，表示数组长度。第二行数据是n个整数a[1], a[2], ..., a[n] (1≤a[i]≤10⁹)。	样例输入 4 2 1 3 4
输出输出“yes”，如果存在；否则输出“no”，不用输出引号。	样例输出 yes
时间限制C/C++语言：1000MS其它语言：3000MS	内存限制C/C++语言：65536KB其它语言：589824KB

思路：

将输入的数组进行排序，然后一边从左边开始，一边从右边开始找出已经拍好序的数字。然后得出了剩下需要翻转的数。剩下的这些需要翻转的数与已经排好序列的逆序比较看能不能全部都相等。

举例1：

1 2 3 4 5

3 2 1 4 5

需要翻转的连续序列是 3 2 1 比较与原来已经排好序（1 2 3 4 5的1 2 3）的逆序（3 2 1）全部相同，所以存在。

代码实现

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
   
  public static void main(String[] args){
   @SuppressWarnings("resource")
Scanner in=new Scanner(System.in);
   while(in.hasNext()){
       int len=in.nextInt();
       int[] array=new int[len];
       int[] Asort=new int[len];
       for(int i=0;i<len;i++){
          array[i]=in.nextInt();
          Asort[i]=array[i];
       }
      Arrays.sort(Asort);
      int left=0,right=len-1;
      while(left<len&&array[left]==Asort[left]) left++;
      while(right>=0&&array[right]==Asort[right]) right--;
      int i;
      for(i=0;i<right-left;i++){
          if(array[left+i]!=Asort[right-i]) break; 
      }
      if(i==right-left) System.out.println("yes");
      else System.out.println("no");
   }
 }
 }