翻转数组(C语言实现)

骑猪看日落 2022-06-08 08:52 234阅读 0赞

## 1、题目描述 ##

给定一个长度为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]。 示例如下：

![20170920182821940][]

## 2、解题思路 ##

要考虑数组整体是升序的，且数组的任意两个元素都不相同，而且是只有一个片段翻转就可以完成数组的升序排列。只要找到第一个降序的子序列对它进行翻转即可，如果翻转后数组有序则输出yes，否者输出no。

## 3、算法实现 ##

#include <stdio.h>
    
    int main()
    {
    	int n;
    	fscanf(stdin, "%d", &n);	/* 输入数组的大小 */
    
    	int i, j;
    	int x;
    	int index, index2;
    	int a[n];
    	for(i = 0; i < n; i++)		/* 依次输入数组的元素 */
    	{
    		fscanf(stdin, "%d", &x);
    		a[i] = x;
    	}
    
    	/* 找到需要翻转的第一个片段的左下标 */
    	x = a[0];
    	index = 0;
    	for(i = 1; i < n; i++)
    	{
    		if(x < a[i])
    		{
    			x = a[i];
    			index = i;
    		}
    		else break;
    	}
    
    	/* 找到需要翻转的第一个片段的右下标 */
    	x = a[index];
    	index2 = index;
    	for(i = index + 1; i < n; i++)
    	{
    		if(x > a[i])
    		{
    			x = a[i];
    			index2 = i;
    		}
    		else break;
    	}
    
    	/* 将找到的这个片段的元素进行翻转 */
    	for(i = index, j = 0; i <= (index2+index)/2; i++, j++)
    	{
    		x = a[index+j];
    		a[index+j] = a[index2-j];
    		a[index2-j] = x;
    	}
    
    	/* 判断是否有奇异数据点，如果没有应该一直找到数组最后一个元素的下标 */
    	x = a[0];
    	index = 0;
    	for(i = 1; i < n; i++)
    	{
    		if(x < a[i])
    		{
    			x = a[i];
    			index = i;
    		}
    		else break;
    	}
    
    	/* 判断是否是最后一个元素的下标 */
    	if(index == n-1)
    		fprintf(stdout, "yes");
    	else 
    		fprintf(stdout, "no");	
    
    	return 0;
    }

[20170920182821940]: /images/20220608/cc13fb8d85d340629c5a72e9210bac26.png