题目描述

给定一个长度为 n 的整数数组 a1,a2,…,an。

请你找到数组中只出现过一次的数当中最小的那个数。

输出找到的数的索引编号。

a1 的索引编号为 1，a2 的索引编号为 2，…，an 的索引编号为 n。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
每组数据输出一行结果，即满足条件的数的索引编号，如果不存在满足条件的数，则输出 −1。

数据范围
1≤T≤2×104,
1≤n≤2×105,
1≤ai≤n,
同一测试点内的所有 n 的和不超过 2×105。

样例

输入样例：
6
2
1 1
3
2 1 3
4
2 2 2 3
1
1
5
2 3 2 4 2
6
1 1 5 5 4 4
输出样例：
-1
2
4
1
2
-1

算法1

(暴力枚举) $O(n^2)$

Go暴力解法

时间复杂度

O(n)

参考文献

Go 在读取第二个数据20w条的时候ReadLine的缓存不够，会导致数据丢失，所以需要用ReadBytes方法读取

Go 代码

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "strconv"
    "strings"
)

var input = bufio.NewReader(os.Stdin)

func main() {
    line, _, err := input.ReadLine()
    if err != nil {
        return
    }
    n, err := strconv.Atoi(string(line))
    for ; n != 0; n-- {
        _, _, err = input.ReadLine()
        if err != nil {
            return
        }
        line, err := input.ReadBytes('\n')
        if err != nil {
            return
        }
        fmt.Println(solve(strings.Split(strings.Replace(string(line), "\n", "", -1), " ")))
    }
}

func solve(strs []string) int {
    mp := make(map[int]int)
    index := make(map[int]int)
    for i, v := range strs {
        key, _ := strconv.Atoi(v)
        if mp[key] == 0 {
            mp[key]++
        } else {
            mp[key] = -1
        }
        index[key] = i + 1
    }
    min := math.MaxInt32
    for k, v := range mp {
        if v != -1 && k < min {
            min = k
        }
    }
    if mp[min] == 0 {
        return -1
    }
    return index[min]
}