头条面试的算法题，怎么解？
头条面试的时候问的算法题：
给定一个乱序的链表，现在有一个操作：可以把链表任意位置的值移动到链表的最后。求链表排序所需要的最少操作次数。
样例：
假如链表的值为：5 1 2 3 那么最少的操作次数为1，直接把5移到最后即可，输出为1.
再比如 链表值为 5 2 1 3 ，那么应该先把2移到最后，再把3移到最后，再把5移到最后，这样输出的结果为3.
怎么解？
#实习##面经#
2018-04-02 15:20 已编辑 华南理工大学 算法工程师
关注
全部评论
DmcDante
上海交通大学 Java
把链表所有值扔到一个最小堆，count计数为0，遍历链表找到和最小堆堆顶元素相等的节点，最小堆出堆，count计数+1，检测当前堆顶是否和下一个节点相等，相等的话重复上述操作，不相等说明链表中从最小节点开始符合全局有序的序列长度为count，需要移动的最小次数是总数n-count 如5 2 1 3 ，第一次堆顶为1，找到链表中1的位置，下一个堆顶元素为2，但是节点的下一个元素为3，不相等，所以最小移动次数为4-1=3，代码中注意下边界条件检测等问题应该就ok
接下来的路才真正的开始
武汉科技大学 C++
举例：5 4 8 9 1 7 6 2 3 本质上就是找到最小的数，然后从最小的数开始一直到后面的最长有序序列。 首先找到最小数1。1左边的肯定要移动，直接不用管。 5 4 8 9 1 6 7 2 3 从1开始，6大于1，标记f1为5，即已排序的下标；标记f2为5，即为已遍历的下标。 7大于6，标记f1为6，f2为6。 2小于6，标记f1位5，f2为7，且序列变为5 4 8 9 1 2 7 2 3 3大于2，标记f1位6，f2为8，且序列变为5 4 8 9 1 2 3 2 3 最后用标记f1，即最后需要找的序列，减去最小数的下标，即为他的长度，也就是最小的数开始一直到后面的最长有序序列的长度m。所以最后的结果为 N（总长度）-m。@尤里卡斯特 中间查找比较的时候可以用二分优化下。。
lzslzslzs
山东农业大学 C++
先遍历一遍找到最小值min1，记录下来。 然后再次遍历，找到min1左边部分的最小值min2。 记录min1右边部分有多少个数大于min2，记为cnt。 最后结果即为 左边部分数量+cnt 时间复杂度为O(n),；使用了3个int（longlong），空间复杂度为常数阶
接下来的路才真正的开始
武汉科技大学 C++
时间空间要求？ 假设 5 4 8 9 1 7 6 3 首先找到排序 1 3 4 5 6 7 8 9 然后和原始数列进行对比发现，从最小数1开始。 发现只有1 3满足要求，即1 3不动， 其他数从小到大依次往后移。 所需移动次数未8-2=6，移动如下： 5 8 9 1 7 6 3 4 8 9 1 7 6 3 4 5 8 9 1 7 3 4 5 6 8 9 1 3 4 5 6 7 9 1 3 4 5 6 7 8 1 3 4 5 6 7 8 9
山柴贩
浙江大学 Java
https://www.nowcoder.com/questionTerminal/adc291e7e79f452c8b59243a5ce68d3a 和这个题类似的
anonk
鄂州职业大学 C++
5 -> 1 -> 2 -> 3 提供参考思路，时间复杂度O(n), 空间复杂度O(1) 1. 找链表的最小值，比如1，指针为lo，count=1 2. 找lo前面的最小值为5，查找一次就ok 3. 从lo开始往后找，找lo后面的最小值为2，对比2和5，比前面的最小值5小，count++，lo设置为2，重复第3步 4. 如果第3步中向后遍历的值比5大，可以结束了，答案就是 链表长度-count。
你有没有问条件，比如这n个数范围，是范围内随机数，还是1-n,是有重复还是没有重复数字，单链表还是双向链表，条件不同，做法就不同
=..=
腾讯_天美_研发工程师(准入职)
空间是O（1）应该是有条件的，猜测是数字从1-n连续，其实就是给了你排好序的数组，把链表遍历一遍，记录不需要变的个数count，n-count就行了
尤里卡斯特 楼主
楼主 华南理工大学 算法工程师
头条的算法题，真难！
加满油go
华南理工大学 算法工程师
我觉得思想可能是首先从最小的数查找，从它开始查看下一个是否是比它大的最小的数，如果是继续寻找，如果不是，1则找到比它大的最小的数把排到最后，然后比他大的都要排一次最后，所以我觉得总次数为：假如前m个数为紧挨升序排列，则最小排列次数为（n-m），n为总个数。
海量hc
中山大学 算法工程师
双指针？空间复杂度O(1)我也不知道 def f(nums):
sortnums = sorted(nums)
n = len(nums)
i = nums.index(min(nums))
j = 0
if i == n - 1:
return n - 1
while i < n and j < n:
if nums[i] == sortnums[j]:
i = i + 1
j = j + 1
else:
i = i + 1
return n - j
小罐球
浙江大学 算法工程师
//找到从最小值开始的最长有序序列，动规遍历一遍，碰到更小的值归零？
int count;
int curmin = 0;
int dp[N];
for(int i = 0; i < N; i++){
if(a[i] > curmin){
if(a[i] > a[i] - 1){
dp[i] = dp[i - 1] + 1;
}
else{
dp[i] = dp[i - 1];
}
}
else{
curmin = i;
dp[i] = 0;
}
}
count = N - dp[N-1];
一个数前面有比它大的数，那么这个大的数必须移一次 找出所有需要移的数，按从小打到依次往后移 用stack来实现
Juliiii
中山大学 C++
头条的算法题真是一题比一题惊心
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享