头条面试的算法题，怎么解？

把链表所有值扔到一个最小堆，count计数为0，遍历链表找到和最小堆堆顶元素相等的节点，最小堆出堆，count计数+1，检测当前堆顶是否和下一个节点相等，相等的话重复上述操作，不相等说明链表中从最小节点开始符合全局有序的序列长度为count，需要移动的最小次数是总数n-count 如5 2 1 3 ，第一次堆顶为1，找到链表中1的位置，下一个堆顶元素为2，但是节点的下一个元素为3，不相等，所以最小移动次数为4-1=3，代码中注意下边界条件检测等问题应该就ok

https://www.nowcoder.com/questionTerminal/adc291e7e79f452c8b59243a5ce68d3a 和这个题类似的

时间空间要求？ 假设 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

先遍历一遍找到最小值min1，记录下来。 然后再次遍历，找到min1左边部分的最小值min2。 记录min1右边部分有多少个数大于min2，记为cnt。 最后结果即为 左边部分数量+cnt 时间复杂度为O(n),；使用了3个int（longlong），空间复杂度为常数阶

举例：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。@尤里卡斯特 中间查找比较的时候可以用二分优化下。。  

头条的算法题真是一题比一题惊心

一个数前面有比它大的数，那么这个大的数必须移一次 找出所有需要移的数，按从小打到依次往后移 用stack来实现

//找到从最小值开始的最长有序序列，动规遍历一遍，碰到更小的值归零？ 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];

双指针？空间复杂度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

我觉得思想可能是首先从最小的数查找，从它开始查看下一个是否是比它大的最小的数，如果是继续寻找，如果不是，1则找到比它大的最小的数把排到最后，然后比他大的都要排一次最后，所以我觉得总次数为：假如前m个数为紧挨升序排列，则最小排列次数为（n-m），n为总个数。

头条的算法题，真难！

空间是O（1）应该是有条件的，猜测是数字从1-n连续，其实就是给了你排好序的数组，把链表遍历一遍，记录不需要变的个数count，n-count就行了

你有没有问条件，比如这n个数范围，是范围内随机数，还是1-n,是有重复还是没有重复数字，单链表还是双向链表，条件不同，做法就不同

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。