Java研发岗面试经典：寻找首个仅出现一次的字符

Java研发岗的经典编程题通常包括对基础编程技能和算法理解的考察，例如在这个特定的问题中，题目是寻找一个字符串中第一个只出现一次的字符。这个问题涉及到了数据结构和哈希表的应用，以及时间复杂度的分析。 首先，题目要求解决的是在给定的字符串中找到第一个只出现一次的字符。这是一个常见的编程面试问题，因为它测试了候选人的逻辑思维、查找算法和对哈希表（或散列表）的理解。哈希表是一种高效的数据结构，它能够通过键（这里是字符）快速查找对应的值（字符出现的次数）。 为了实现这个功能，我们需要进行两次遍历字符串。第一次遍历（预处理阶段）时，使用一个大小为256的数组（哈希表）来记录每个字符的出现次数，因为ASCII码的范围正好是0-255。对于输入的每个字符，我们在哈希表中相应位置的计数器加1，这个操作的时间复杂度是O(n)，其中n是字符串的长度。 第二次遍历（查找阶段）时，从字符串的开始重新扫描，当遇到的字符在哈希表中的计数为1时，说明该字符只出现了一次，满足题目要求。这次遍历的时间复杂度同样为O(n)，因为在最坏的情况下，我们可能需要检查整个字符串。总的时间复杂度是O(n)，这是在理想情况下，没有冲突（即多个键映射到同一位置）的情况。 以下是用C++实现的代码片段： ```cpp #include<stdio.h> #include<stdlib.h> #include<string.h> char FirstNotRepeatingChar(char* pString) { if (pString == NULL) { return '\0'; } const int tableSize = 256; unsigned int hasTable[tableSize] = {0}; // 初始化哈希表 unsigned int i = 0; for (i = 0; i < tableSize; i++) { hasTable[i] = 0; } char* pHashKey = pString; while (*pHashKey != '\0') { hasTable[*pHashKey]++; pHashKey++; } pHashKey = pString; while (*pHashKey != '\0') { if (hasTable[*(pHashKey)] == 1) { return *pHashKey; // 返回第一个只出现一次的字符 } pHashKey++; } // 如果没有找到只出现一次的字符，返回空格或特殊值 return '\0'; // 或者可以返回一个特定标记，表示没有找到 } ``` 解决这个问题的关键在于使用哈希表有效地统计字符出现的频率，并在第二次遍历时找到第一个出现次数为1的字符。这个过程体现了Java程序员在实际工作中可能面临的字符串处理和数据结构运用挑战，是评估候选人编码能力和算法基础的重要参考题型。