剑指offer-34、第⼀次出现的字符
<h2 id="题目描述">题目描述</h2><p>在⼀个字符串( 0<=字符串⻓度<=10000 ，全部由字⺟组成)中找到第⼀个只出现⼀次的字符,并返回它的位置, 如果没有则返回 -1 （需要区分⼤⼩写）.（从 0 开始计数）</p>
<p>示例1<br>
输⼊："google"<br>
返回：4</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力遍历不推荐">暴力遍历（不推荐）</h3>
<p>通过双重循环检查每个字符是否只出现一次。</p>
<pre><code class="language-java">public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
for (int i = 0; i < str.length(); i++) {
char currentChar = str.charAt(i);
boolean isUnique = true;
// 检查当前字符是否在后续或前面重复出现
for (int j = 0; j < str.length(); j++) {
if (i != j && currentChar == str.charAt(j)) {
isUnique = false;
break; // 发现重复，立即跳出内层循环
}
}
if (isUnique) {
return i; // 返回第一个唯一字符的位置
}
}
return -1; // 没有找到唯一字符
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，其中n是字符串长度。对于每个字符，都需要遍历整个字符串检查是否重复</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了常数级别的额外空间</li>
</ul>
<h3 id="哈希表统计次数">哈希表统计次数</h3>
<p>使用HashMap来统计每个字符的出现次数，然后按顺序查找第一个出现次数为1的字符</p>
<pre><code class="language-java">import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
// 使用HashMap统计每个字符的出现次数
HashMap<Character, Integer> charCount = new HashMap<>();
// 第一次遍历：统计字符出现次数
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// 第二次遍历：按原顺序查找第一个出现次数为1的字符
for (int i = 0; i < str.length(); i++) {
if (charCount.get(str.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要两次线性遍历</li>
<li><strong>空间复杂度</strong>：O(n)</li>
</ul>
<h3 id="使字符数组来统计">使⽤字符数组来统计</h3>
<p>由于全都是字符，’ A ‘-’ z ‘⼀共 58 个字符（中间有其他字符）,针对已知字符范围的情况，可以用数组代替HashMap，提高效率</p>
<pre><code class="language-java">public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) return -1;
// 由于要区分大小写，且包含所有字母，使用128覆盖基本ASCII字符
int[] charCount = new int;
// 第一次遍历：统计字符出现次数
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
charCount++;
}
// 第二次遍历：查找第一个唯一字符
for (int i = 0; i < str.length(); i++) {
if (charCount == 1) {
return i;
}
}
return -1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)</li>
<li><strong>空间复杂度</strong>：O(1)，数组大小固定为128</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19137127
頁:
[1]