哈希表题目:保证文件名唯一
文章目录
- 题目
-
- 标题和出处
- 难度
- 题目描述
-
- 要求
- 示例
- 数据范围
- 解法
-
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:保证文件名唯一
出处:1487. 保证文件名唯一
难度
5 级
题目描述
要求
给你一个长度为 n\\texttt{n}n 的字符串数组 names\\texttt{names}names。你将会在文件系统中创建 n\\texttt{n}n 个文件夹:在第 i\\texttt{i}i 分钟,新建名为 names[i]\\texttt{names[i]}names[i] 的文件夹。
由于两个文件不能共享相同的文件名,因此如果新建文件夹使用的文件名已经被占用,系统会以 (k)\\texttt{(k)}(k) 的形式为新文件夹的文件名添加后缀,其中 k\\texttt{k}k 是能保证文件名唯一的最小正整数。
返回长度为 n\\texttt{n}n 的字符串数组,其中 ans[i]\\texttt{ans[i]}ans[i] 是创建第 i\\texttt{i}i 个文件夹时系统分配给该文件夹的实际名称。
示例
示例 1:
输入:names=["pes","fifa","gta","pes(2019)"]\\texttt{names = ["pes","fifa","gta","pes(2019)"]}names = ["pes","fifa","gta","pes(2019)"]
输出:["pes","fifa","gta","pes(2019)"]\\texttt{["pes","fifa","gta","pes(2019)"]}["pes","fifa","gta","pes(2019)"]
解释:文件系统将会这样创建文件名:
"pes"→\\texttt{"pes"} \\rightarrow"pes"→ 之前未分配,仍为 "pes"\\texttt{"pes"}"pes"。
"fifa"→\\texttt{"fifa"} \\rightarrow"fifa"→ 之前未分配,仍为 "fifa"\\texttt{"fifa"}"fifa"。
"gta"→\\texttt{"gta"} \\rightarrow"gta"→ 之前未分配,仍为 "gta"\\texttt{"gta"}"gta"。
"pes(2019)"→\\texttt{"pes(2019)"} \\rightarrow"pes(2019)"→ 之前未分配,仍为 "pes(2019)"\\texttt{"pes(2019)"}"pes(2019)"。
示例 2:
输入:names=["gta","gta(1)","gta","avalon"]\\texttt{names = ["gta","gta(1)","gta","avalon"]}names = ["gta","gta(1)","gta","avalon"]
输出:["gta","gta(1)","gta(2)","avalon"]\\texttt{["gta","gta(1)","gta(2)","avalon"]}["gta","gta(1)","gta(2)","avalon"]
解释:文件系统将会这样创建文件名:
"gta"→\\texttt{"gta"} \\rightarrow"gta"→ 之前未分配,仍为 "gta"\\texttt{"gta"}"gta"。
"gta(1)"→\\texttt{"gta(1)"} \\rightarrow"gta(1)"→ 之前未分配,仍为 "gta(1)"\\texttt{"gta(1)"}"gta(1)"。
"gta"→\\texttt{"gta"} \\rightarrow"gta"→ 文件名被占用,系统为该名称添加后缀 (k)\\texttt{(k)}(k),由于 "gta(1)"\\texttt{"gta(1)"}"gta(1)" 也被占用,所以 k=2\\texttt{k = 2}k = 2。实际创建的文件名为 "gta(2)"\\texttt{"gta(2)"}"gta(2)"。
"avalon"→\\texttt{"avalon"} \\rightarrow"avalon"→ 之前未分配,仍为 "avalon"\\texttt{"avalon"}"avalon"。
示例 3:
输入:names=["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]\\texttt{names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]}names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出:["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]\\texttt{["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]}["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释:当创建最后一个文件夹时,最小的正有效 k\\texttt{k}k 为 4\\texttt{4}4,文件名变为 "onepiece(4)"\\texttt{"onepiece(4)"}"onepiece(4)"。
数据范围
- 1≤names.length≤5×104\\texttt{1} \\le \\texttt{names.length} \\le \\texttt{5} \\times \\texttt{10}^\\texttt{4}1≤names.length≤5×104
- 1≤names[i].length≤20\\texttt{1} \\le \\texttt{names[i].length} \\le \\texttt{20}1≤names[i].length≤20
- names[i]\\texttt{names[i]}names[i] 由小写英语字母、数字和/或圆括号组成
解法
思路和算法
由于每个文件夹的文件名必须各不相同,因此在创建文件夹时,需要判断原始文件名是否被占用,如果被占用,需要找到最小的正整数 kkk 并以后缀的形式添加到文件名后面,使得实际名称不被占用。
为了判断原始文件名是否被占用和找到保证文件名唯一的最小正整数 kkk,需要使用哈希表记录每个原始文件名的使用次数。如果原始文件名不在哈希表中,则原始文件名没有被占用,不需要添加后缀;如果原始文件名在哈希表中且使用次数是 kkk,则需要在原始文件名后面添加后缀 (k)(k)(k),然后在哈希表中将原始文件名的使用次数加 111。
上述思路并不能保证文件名唯一,因为添加后缀 (k)(k)(k) 之后得到的实际名称仍可能已经被占用。示例 2 就存在这样的情况,当遍历到 names[2]=“gta"\\textit{names}[2] = \\text{``gta"}names[2]=“gta" 时,虽然哈希表中 “gta"\\text{``gta"}“gta" 的使用次数是 111,但是 “gta(1)"\\text{``gta(1)"}“gta(1)" 已经被占用,因此 k=1k = 1k=1 并不能保证文件名唯一,需要将 kkk 的值增加到 222 才能保证文件名唯一。示例 3 也存在这样的情况,当遍历到 names[4]=“onepiece"\\textit{names}[4] = \\text{``onepiece"}names[4]=“onepiece" 时,虽然哈希表中 “onepiece"\\text{``onepiece"}“onepiece" 的使用次数是 111,但是 “onepiece(1)"\\text{``onepiece(1)"}“onepiece(1)" 已经被占用,“onepiece(2)"\\text{``onepiece(2)"}“onepiece(2)" 和 “onepiece(3)"\\text{``onepiece(3)"}“onepiece(3)" 也已经被占用,因此 k=1,2,3k = 1, 2, 3k=1,2,3 都不能保证文件名唯一,需要将 kkk 的值增加到 444 才能保证文件名唯一。
因此,为了保证文件名唯一,当使用次数是 kkk 时,需要判断添加后缀 (k)(k)(k) 之后的实际名称是否被占用,如果实际名称仍被占用则需要增加 kkk 的值,直到添加后缀 (k)(k)(k) 之后的实际名称不被占用。
还需要注意的一点是,如果一个文件夹的文件名添加了后缀,则添加后缀之后的实际名称也会影响到后续创建的文件夹的命名,因此也需要将实际名称添加到哈希表中,由于添加后缀之后的实际名称第一次出现,因此实际名称在哈希表中的使用次数是 111。考虑以下例子:names=[“name", “name", “name(1)"]\\textit{names} = [\\text{``name", ``name", ``name(1)"}]names=[“name", “name", “name(1)"]。为了保证文件名唯一,names[1]\\textit{names}[1]names[1] 需要变成 “name(1)"\\text{``name(1)"}“name(1)",当遍历到 names[2]=“name(1)"\\textit{names}[2] = \\text{``name(1)"}names[2]=“name(1)" 时,该名称已经被 names[1]\\textit{names}[1]names[1] 的实际名称占用,因此 names[2]\\textit{names}[2]names[2] 需要变成 “name(1)(1)"\\text{``name(1)(1)"}“name(1)(1)"。
根据上述分析,遍历每个文件名时,保证文件名唯一的做法如下:
-
如果原始文件名不在哈希表中,则原始文件名没有被占用,因此实际名称即为原始文件名,并将原始文件名和使用次数 111 存入哈希表;
-
如果原始文件名已经在哈希表中,则原始文件名已经被占用,从哈希表中得到原始文件名的使用次数 kkk,并判断添加后缀 (k)(k)(k) 之后的实际名称是否被占用,如果被占用则增加 kkk 的值,直到添加后缀 (k)(k)(k) 之后的实际名称不被占用,然后在哈希表中将原始名称的使用次数更新为 k+1k + 1k+1,并将实际名称和使用次数 111 存入哈希表。
代码
class Solution {public String[] getFolderNames(String[] names) {int n = names.length;String[] ans = new String[n];Map<String, Integer> map = new HashMap<String, Integer>();for (int i = 0; i < n; i++) {String name = names[i];if (!map.containsKey(name)) {ans[i] = name;map.put(name, 1);} else {int k = map.get(name);while (map.containsKey(name + "(" + k + ")")) {k++;}String actualName = name + "(" + k + ")";ans[i] = actualName;map.put(name, k + 1);map.put(actualName, 1);}}return ans;}
}
复杂度分析
-
时间复杂度:O(n)O(n)O(n),其中 nnn 是数组 names\\textit{names}names 的长度。需要遍历数组 names\\textit{names}names 生成每个文件名的实际名称,在添加后缀时需要确定最小的正整数 kkk,由于在确定 kkk 的值时每个实际名称最多被遍历一次,因此总时间复杂度是 O(n)O(n)O(n)。这里将字符串操作的时间视为 O(1)O(1)O(1)。
-
空间复杂度:O(n)O(n)O(n),其中 nnn 是数组 names\\textit{names}names 的长度。需要使用哈希表记录每个文件名的使用次数,由于每个实际名称都需要记录,因此哈希表中的元素个数是 nnn。这里将字符串占用的空间视为 O(1)O(1)O(1)。