今天下午师兄在教研室群里发了一道热乎的广联达算法题,乍一看完全没有思路,于是实验室的小伙伴们饶有兴致地开始讨论起了这道题。
先给大家看一下题目:
题目描述
有一种排序算法定义如下,该排序算法每次把一个元素提到序列的开头,例如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技术修炼指南
今天的文章一道广联达秋招算法题分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/28920.html