时间戳

首页 > 解决方案 > 使用哈希映射在c ++中查找字符串中的第一个唯一元素的问题

c++ - 使用哈希映射在c ++中查找字符串中的第一个唯一元素的问题

问题描述

int firstUniqChar(std::string s) {
    //Using maps to find the first unique character of the string
    int string_len;
    int pos;
    std::unordered_map<char, int> m{};
    string_len = s.size();

    for (int i = 0; i < string_len; i++) {
        //if the char in string is not present in map, then add to the map with a 
        //frequency of 1.
        if(m.find(s[i]) == m.end()) {
            m.insert(std::make_pair(s[i], 1));
        } else {
            m[s[i]]++;            
        }
    }     
    
    for(std::unordered_map<char, int>::iterator it = m.begin(); it != m.end(); ++it) {
        if (it->second == 1) {
           int index = std::distance(m.begin(), it);                
            return index;
        }
    }

    return -1;
}

我正在尝试使用 C++ 中的映射来查找字符串中的第一个唯一元素。虽然我能够计算元素的频率，但代码不会返回第一个唯一元素。与地图中的排序有关。我如何获得第一个独特的元素。

添加另一个不涵盖所有情况的数组代码

int main() {
std::string s = "aadadaad";
int len = s.length();

if (len == 1) {
    return 0;
}

for (int i = 0; i < len; i++) {
    bool found = true;
    for (int j = i + 1; j < len; j++) {
        if (s[i] == s[j]) {
            found = false;
            break;
        }
    }

    if ((i != len - 1) && (found == true)) {
        std::cout << i << std::endl;
        return i;
    }
}

std::cout << "-1" << std::endl;
return -1;

}

标签： c++c++14

解决方案

您返回的是无序地图的第一个元素。第一个元素与字符串的第一个唯一元素无关。

你应该做的是，一旦你计算了频率，再次迭代字符串并返回频率为 1 的第一个字符。

PS 如果您可以假设一个 8 位字节 - 这可能是一个合理的假设 - 那么只有 256 个不同的值。一个可能更有效的解决方案是使用 256 个元素的数组，而不是 hashmap。请注意，您需要转换为 unsigned char 才能使用字符作为索引。

推荐阅读