[23]序列操作-美团点评2018秋

1.题目描述

有一天你得到了一个长度为 n 的序列，序列中的元素分别为 1,2,3，…,n。接下来你想对这个 序列进行一些操作。每一操作你会选择一个数然后将它从序列中原来的位置取出并放在序列的最前面。你 想知道经过一系列操作后这个序列长什么样。

• 输入描述：
  第一行包含两个个整数 n、m，分别标书序列的长度和操作的个数。1≤n，m≤105，接下来 m 行每行包含一
  个整数 ki，表示你要把 ki放到序列的最前面。1≤ki≤n
• 输出描述：
  从前往后输出序列中的每个元素，每个元素占一行。
• 输入样例：

  5 3 
  4 
  2
  5 
  

• 输出样例：

  5 
  2 
  4 
  1 
  3
  

2.题目解析

从题目本身看，容易得出数组移动的处理方式，但是效率比较低

#include <bits/stdc++.h>
using namespace std;

void move(int *arr, int n, int num) {

  // 查找位置
  int pos = 0;
  for(int i=0;i!=n;++i){
    if(arr[i] == num){
      pos = i;
      break;
    }
  }

  // 位置前的向后移动
  for(int i=pos;i!=0;--i){
    arr[i] = arr[i-1];
  }
  arr[0] = num;
}

int main() {
  int n = 0;
  int m = 0;
  scanf("%d%d",&n,&m);
  
  // 初始化数列
  int arr[n];
  for(int i=0;i!=n;++i){
    arr[i] = i+1;
  }

  // 获取移动数据
  while(m--){
    int num = 0;
    scanf("%d", &num);
    move(arr, n, num);
  }

  // 打印移动结果
  for (int i = 0; i != n; ++i) {
    printf("%d\n",arr[i]);
  }
  return 0;
}

数组易查不易动，链表易动不易查。

• 优化效率
  线性双向链表：连续内存的双向链表，以下标作为连接。

3.参考答案

#include <bits/stdc++.h>
using namespace std;
struct Node{
  int prev; // 前一个数据
  int post; // 后一个数据
};

void Print(Node* nodes,int n,int head){
    int now = head;
    while(now != n+1){
        printf("%d\n",now);
        now = nodes[now].post; // 向后遍历
    }
}
int main() {
    int n = 0;
    scanf("%d",&n);
    Node nodes[n+1];
    // prev为0表示开始
    // post为n+1表示结束
    for(int i=1;i<=n;++i){
        nodes[i].prev = i-1;
        nodes[i].post = i+1;
    }
    // 遍历链表
    int head = 1;
    int m = 0;
    scanf("%d",&m);
    
    for(int i=0;i<m;++i){
        int move = 0;
        scanf("%d",&move);
        if(move == head) continue; // 如果要移动的数据已经在头节点，不处理
        int prev = nodes[move].prev;
        int post = nodes[move].post;
        nodes[prev].post = post;
        nodes[post].prev = prev;
        nodes[move].prev = 0;
        nodes[move].post = head;
        nodes[head].prev = move;
        head = move; //  更换头节点下标
    }
    Print(nodes,n,head);
}

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 0;
  int m = 0;
  scanf("%d%d",&n,&m);

  // 位置记录(数字与下标保持一致，下标0不使用)
  // 设定第一个数的prev为0，最后一个数的next为n+1
  int prev[n+1];
  int next[n+1];
  for(int i=1;i!=n+1;++i){
    prev[i] = i-1;
    next[i] = i+1;
  }

  int top = 1;// 顶部数字
  
  // 移动
  while(m--){
    int num;// 移动的数字
    scanf("%d",&num);
    
    if(num == top){// 数字在顶不处理
        continue;
    }
    // 把前面的与后面连在一起
    next[prev[num]] = next[num];
    // 把后面的与前面连在一起
    prev[next[num]] = prev[num];
    
    // 修改当前数字的连接
    prev[num] = 0;
    next[num] = top;

    // 修改顶部的连接
    prev[top] = num;

    // 当前数字作为新的顶部
    top = num;
  }

  // 打印结果
  for(int i = 0;i!=n;++i){
    printf("%d\n",top);
    top = next[top]; // 依次移动top
  }
  
  return 0;
}

• 牛客题目