【LeetCode】数组中第 K 个独一无二的字符串 Java 题解

2022 年 6 月 05 日
本文字数：994 字
阅读完需：约 3 分钟

题目描述

独一无二的字符串指的是在一个数组中只出现过一次的字符串。

给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个独一无二的字符串。如果少于 k 个独一无二的字符串，那么返回空字符串 "" 。

注意，按照字符串在原数组中的顺序找到第 k 个独一无二字符串。


示例 1:
输入：arr = ["d","b","c","b","c","a"], k = 2输出："a"解释：arr 中独一无二字符串包括 "d" 和 "a" 。"d" 首先出现，所以它是第 1 个独一无二字符串。"a" 第二个出现，所以它是 2 个独一无二字符串。由于 k == 2 ，返回 "a" 。
示例 2:
输入：arr = ["aaa","aa","a"], k = 1输出："aaa"解释：arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 "aaa" 。
示例 3：
输入：arr = ["a","b","a"], k = 3输出：""解释：唯一一个独一无二字符串是 "b" 。由于少于 3 个独一无二字符串，我们返回空字符串 "" 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/kth-distinct-string-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串处理题目。分析题目，需要找到字符串在原数组中的顺序找到第 k 个独一无二字符串。
我们首先需要找到独一无二字符串，也就是只出现一次的字符串，应用到记数问题，首先想到的是数组记数或者 hashmap 计数。这个题目的 key 是字符串，使用 hashmap 比较合适。
这个题目第二点是要求按照字符串的原顺序，我们使用 hashmap 的时候，单字符的顺序会重新排列，因此，我们再次遍历整个字符串，找到字符出现 1 次的字符串。实现代码如下，请参考。

通过代码

class Solution {    public String kthDistinct(String[] arr, int k) {        Map<String, Integer> map = new HashMap<>();        for (String str : arr) {            map.put(str, map.getOrDefault(str, 0) + 1);        }
        String ans = "";        int cnt = 0;         for (String str : arr) {            if (map.get(str) == 1) {                cnt++;                if (cnt == k) {                    ans = str;                    break;                }            }        }
        return ans;   
    }}