dmy#104

[R18B]项链

难度入门
时限 1s
空限 512m
模拟哈希

数据规模： $1 \le n,m \le 3 \times 10^5$ ， $1 \le a_i \le m$ 。

思路

每种颜色要取「编号最小」的那颗珠子，而珠子是按编号 $1 \sim n$ 顺序给出的。因此只要从左到右扫描一遍，对每种颜色记录是否已经第一次出现：第一次见到颜色 $c$ 时就把当前编号记下，之后同色珠子一律跳过。

由于扫描方向本身就是编号递增的方向，第一次见到的那个就是该颜色的最小编号；并且记录下来的编号也自然按从小到大的顺序排列，无需再排序。

用一个大小为 $m+1$ 的布尔数组 seen 标记每种颜色是否已出现，边扫描边直接用 println 输出即可。

复杂度

时间 $O(n)$ ，空间 $O(n + m)$ 。

仓颉实现

查看仓颉实现

import std.env.*
import std.convert.*

main() {
    let reader = getStdIn()
    let line = reader.readln().getOrThrow().split(" ", removeEmpty: true)
    let n = Int64.parse(line[0])
    let m = Int64.parse(line[1])
    let a = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })

    let seen = Array<Bool>(m + 1, { _ => false })
    var first = true
    for (i in 0..n) {
        let c = a[i]
        if (!seen[c]) {
            seen[c] = true
            if (first) {
                print(i + 1)
                first = false
            } else {
                print(" ")
                print(i + 1)
            }
        }
    }
    println()
}