那些插队的人

关键点都在代码注释里了

package main

/**
  * 计算有多少个人最终不在自己原来的位置上
  * @param n int整型 队伍总长
  * @param cutIn int整型一维数组 依次会插队到最前方的人的编号
  * @return int整型
*/
func countDislocation( n int ,  cutIn []int ) int {
    // write code here
    m := len(cutIn)
    if m == 0 {
        return 0
    }

    appeared := make(map[int]bool)
    curIndex := 1
    cnt := 0
    //统计位置没有发生变化的人数
    maxIndex := cutIn[0]  
    //插队序列最大编号
    for i := m-1; i >= 0; i-- {
        if !appeared[cutIn[i]] {
            appeared[cutIn[i]] = true
            if cutIn[i] == curIndex {
                cnt++
            }
            curIndex++

            if cutIn[i] > maxIndex {
                maxIndex = cutIn[i]
            }
        }
    }
    return maxIndex-cnt
    //大于插队中最大编号的序列都是正确的，因此在发生插队行为这一段中，减去位置正确的，就是位置发生了改变的。
}