在已排序数组中寻找两个被交换的数

Find 2 elements swapped in a sorted array

99. 恢复二叉搜索树

无论在升序数组还是降序数组中, 如果两个数被交换那么一定符合一个规律

在一个升序数组中, 所有的数一定都符合 a[i] < a[i + 1];

如果某两个数被交换, 那么一定符合 a[i] > a[i + 1]

当表达式第一次匹配时, 第一个要找的数是 i ;

表达式第二次被匹配时, 第二个要找的数就是 i + 1

至此匹配结束

void findTwoSwapped(int *arr, int size)
{
	int x = - 1;
	int y = -1;
 
	int i;
	for(i  = 0; i < size -1; ++i)
	{
		if( arr[i+1] < arr[i])
		{
      // 每次匹配时都分别将i + 1作为第二个被交换的元素
			y = i + 1;
      
      // 第一次被匹配时, x没有赋值, 将i赋给x
			if( x == -1)
			{
				x = i;
			}
			else
			{
				break;
			}
		}
	}
 
	int tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;
}