一道广联达秋招算法题

一道广联达秋招算法题今天下午师兄在教研室群里发了一道热乎的广联达算法题,乍一看完全没有思路,于是实验室的小伙伴们饶有兴致地开始讨论起了这道题。先给大家看一下题目:题目描述有一种排序算法定义如下,该排序算法每次把一个元素提到序列的开头,例如2,1,3,4,只需要一次操作把1提到序列起始位置就可以使得原序列从小到大有序。现在给你个乱序的1-n的排列,请你计算最少需要多少次操作才可以使得原序列从小到大有序。输入描述输入第一行包含两个正整数n,表示序列的长度。(1<=n<=100000)接下

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

一道广联达秋招算法题

先给大家看一下题目:

题目描述

有一种排序算法定义如下,该排序算法每次把一个元素提到序列的开头,例如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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注