alicode47-超车

 1 package solution47;
 2 import java.util.*;
 3 class Solution {
 4     public int solution(int n, int[] nums1, int[] nums2) {
 5         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 6         for (int i = 0; i < n; i++) {
 7             map.put(nums2[i], i);
 8         }
 9         int rightIndex = -1;
10         int count = 0;
11         for (int i = 0; i < n; i++) {
12             int cur = nums1[i];
13             int position = map.get(cur);
14             if (i == 0) {
15                 // 当前车手是第一，不可能超车
16                 rightIndex = position;
17             } else {
18                 // 当前车手的最终排名更靠前，说明超车
19                 if (position < rightIndex) {
20                     count += 1;
21                 } else {
22                     // 当前车手的最终排名靠后，没有超车，但是当前车手是在最终排名中的最末尾的人
23                     rightIndex = position;
24                 }
25             }
26         }
27         return count;
28     }
29 }

算法思路：hash。

先根据最终队列，使用hashmap存储每一个车手的最终位置。

再遍历初始队列，计算在初始队列中，当前车手的前面的所有车手在最终队列中的最末尾的人的位置。

如果当前车手比这个最末尾的人的位置排名考前(index更小)，则说明这个人超车了。

遍历过程中，更新这个前序队列中最末尾的人的index。