P132. 第一个只出现一次的字符

https://algocasts.io/episodes/Y9pJkYWA

请问:第二种解法中,创建int[] pos后,默认的值都是0,那后面判断是否第一次出现就直接用pos[idx]==0。所以用Arrays.fill(pos, -1)是为了避免什么corner case么?
谢谢

@ky

由于 pos 中存储的是下标,而 0 是一个合法的下标值,如果让默认的 0 作为不合法初值,这样就会有歧义,所以这里使用了 Arrays.fill(pos, -1)

如果纯粹从输出结果的正确性来讲,直接使用初值 0 应该也是没问题的。

懂了。多谢!

@Hawstein
本题用到的是数组,为啥会出现在哈希表的类别里呀?

@jettsai

因为本质上我们是在使用哈希表这种具有映射关系的数据结构,来统计「字符」 与「出现次数」的映射关系。比如例子中的 apple,「字符」与「出现次数」的映射关系是:

'a' -> 1
'p' -> 2
'l' -> 1
'e' -> 1

因此这个题目中,更通用的辅助数据结构应该是「哈希表」。但由于题目限定了字符集是 26 个小写字母,所以我们才用数组来模拟哈希表,使得辅助数据结构更加简单。

P.S. 用数组模拟哈希表这种小技巧,在很多题目中都可以看到。