一道广联达秋招算法题

今天下午师兄在教研室群里发了一道热乎的广联达算法题，乍一看完全没有思路，于是实验室的小伙伴们饶有兴致地开始讨论起了这道题。

先给大家看一下题目：

题目描述

有一种排序算法定义如下，该排序算法每次把一个元素提到序列的开头，例如2, 1, 3, 4，只需要一次操作把1提到序列起始位置就可以使得原序列从小到大有序。
现在给你个乱序的1-n的排列，请你计算最少需要多少次操作才可以使得原序列从小到大有序。

输入描述

输入第一行包含两个正整数n，表示序列的长度。（1 <= n <= 100000）
接下来一行有n个正整数，表示序列中的n个元素，中间用空格隔开。（1 <= a_i <= n）

输出描述

输出仅包含一个整数，表示最少的操作次数。

样例输入

4
2 1 3 4

样例输出

1

以上就是这道题的题干，说实话，第一眼看过去我甚至觉得这是到冒泡排序。但仔细一看，每个数必须要移动到序列起始位置。

忽然，一个想法闪过我的脑海。

我是这样想的：当一个数被移动到序列的起始位置，那么意味着所有比它小的数都要移动到起始位置。

举个栗子，我们看一下下面一组序列。

2 5 3 1 4 6 7 8

直观地看，我们首先需要把4移到最前面，再把3移到最前面，接着是2和1两个数移到最前面。

看到这里，大家应该看明白了。我们需要与排序后的数组对比，从后往前进行对比，看看哪个数没有在它的相对位置上。以上面的序列为例，这里说的相对位置可以理解为我们从后往前搜索分别能找到8、7、6、5，但是理应在5前面的4却不见了，所以4是不在相对位置上的。因此4需要挪到最前面，在4前面的3、2、1也需要移到最前面。于是我们需要返回至少需要移动四次。

代码如下：

public class Solution {
	public int fun(int n, int[] arr) {
		int[] sortArr = Arrays.copyOf(arr, n);
		Arrays.sort(sortArr);
		int p = n - 1, q = n - 1;
		while (p >= 0 && q >= 0) {
			if (arr[p] == sortArr[q]) {
				--p;
				--q;
			} else {
				while (p >= 0 && arr[p] != sortArr[q]) {
					--p;
				}
			}
		}
		return q + 1;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = in.nextInt();
		}
		
		Solution s = new Solution();
		System.out.println(s.fun(arr.length, arr));
	}
}

由于没有OJ环境，以上代码仅仅测试了我自己输入的部分测试用例。各位如果发现有什么问题可以在下方进行留言与我交流。

欢迎关注我的公众号：SKY技术修炼指南