【每日一题】- 2020-08-28 - [编程题]队列最小修改 （京东2019春招京东前端开发类试卷最后一题）

[azl397985856]

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 64M，其他语言128M

已知一个奇怪的队列，这个队列中有n个数，初始状态时，顺序是1,2,3,4,…n，是1-n按顺序排列。这个队列只支持一种操作，就是把队列中的第i号元素提前到队首(1<i<=n)，如有4个元素，初始为1，2，3，4,可以将3提前到队首，得到3，1，2，4 。 现在给出一个经过若干次操作之后的序列，请你找出这个序列至少是由原序列操作了多少次得到的。

输入描述:
第一行是一个整数n(1<=n<=10^5)，表示序列中数字的数量。 接下来一行有n个数，是1-n的一个全排列。数字之间用空格隔开。

输出描述:
输出仅包含一个数字，表示至少操作了几次

输入例子1:
5
5 2 1 3 4

输出例子1:
2

原题地址：https://www.nowcoder.com/question/next?pid=16778547&qid=370630&tid=36628638

[wycyftk]

因为每次会将一个值提到队列首，那么没有被移动的数字会依然保持原本的顺序。根据这一点，就可以得到结果。代码如下：

def minModify(nums):
  l = len(nums)

  if l <= 1:
    return 0

  for i in range(l - 1, 0, -1):
    if nums[i] < nums[i - 1]:
      return i

时间复杂度：O(n)，当没有数字被移动过时，会遍历整个数组。n是数组长度
空间复杂度：O(1)，只使用了常数个变量

[feikerwu]

算法思路:

1. 因为原来的数组是有序的，而每次操作都是将一个数提到队首，所以剩下的数肯定是有序的
2. 通过1，可以知道我们至少得通过 maybe = n - len(队尾有序子序列). 这是一个下界，也就是我们想要的结果result >= maybe
3. 直觉这个maybe就是我们的答案，但是我们得证明，或者说找到一种提数方案，使得maybe次操作就可以达到给定序列
4. 原始序列被分成[无序序列，剩余有序序列]两个part，贪心法根据无序序列倒序提数即可maybe次操作生成给定序列
5. maybe 就是 result

function solution(n, nums) {
  for (let i = nums.length - 1; i > 0; i--) {
    if (nums[i] < nums[i - 1]) {
      return i
    }
  }
  return 0
}

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.