查找一个字符串是否有相同的字符

查找一个字符串是否有相同的字符 写一个函数，查找一个字符串是否有相同的字符，从效率和空间考虑各写一个 效率高的:用char类型的整个取值范围作下标构造一个大数组，初始化成全0，然 后每扫描一个字符，就把它对应的那项加1，如果有某个项变成2了，就说明有重复字符。 空间省的:利用两重循环，把字符串所有的位置上的字符都两两进行比较。 给你一例: CString str = "sfgtfhh"; LPCTSTR p = str; int i = 0; while (p[i] != '\0') { int k = str.Find(p[i],i+1); if (k != -1) { CString s; s.Format("%c",p[i]); AfxMessageBox(s);//输出重复字符 } i++; } =============================================================== ======= #include #include #include #include #include using namespace std; bool has_repeated_char_space_efficient(const char* s); bool has_repeated_char_time_efficient(const char* s); void time_test(bool (*f)(const char*), const char* name); int main() { time_test(has_repeated_char_space_efficient, "space efficient"); time_test(has_repeated_char_time_efficient, "time efficient"); return 0; } bool has_repeated_char_space_efficient(const char* s) { for(int i = (int)strlen(s) - 1; i > 0; --i) { for(int j = i - 1; j >= 0; --j) { if(s[i] == s[j]) return true; } } return false; } bool has_repeated_char_time_efficient(const char* s) { const unsigned char* p = (const unsigned char*)s; char counters[UCHAR_MAX + 1] = {0}; i = (int)strlen(s); i >= 0; --i) { for(int counters[p[i]]++; if(counters[p[i]] > 1) return true; } return false; } void time_test(bool (*f)(const char*), const char* name) { char* s[] = { "Hello World.", "abcdefghijklmnopqrstuvwxyz", "The C++ Programming Language", "Help Me", "International" }; const int test_count = sizeof(s) / sizeof(*s); bool result[test_count]; clock_t t1 = clock(); for(int i = 0; i < 1000000; ++i) { for(int j = 0; j < test_count; ++j) result[j] = f(s[j]); } clock_t t2 = clock(); copy(result, result + test_count, ostream_iterator(cout, " ")); double t = (t2 - t1) / (double)CLOCKS_PER_SEC; cout << name << ": " << t << " seconds costed." << endl << endl; } ======================================================================================== 实际的测试结果不一定跟预想的完全一致，原因在于: (1)实际中大多数字符串都比较短，甚至好多不超过16个字符的，因此用两重循环也耗不了太多时间; (2)实际中大多数字符串都很容易找到重复字符，那些需要从头看到尾，最终却发现没有一个重复的情况，比较少见。 当然，如果你所处理的字符串不具备上述两条特征，那就另当别论了。 ================================================= “time_efficient”中，这两句: counters[p[i]]++; if(counters[p[i]] > 1) return true; 可以合成一句: if(++counters[p[i]] > 1) return true; 当然，编译器可‎‎能把它们优化成没有区别。 =====================================================