请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。 测试样例： "aeiou" 返回：True "BarackObama" 返回：False
方式三：基于快速排序的partition，可以边排序边找重复，也即是每次partition之后，判断中间key元素与两边元素是否相同，相同则返回false，不同再进行下一轮partition.时间复杂度也是O(nlongn)
#include<iostream> using namespace std; #include<string> #include<algorithm> //方式一 /*bool CheckDifferent(string iniString) { unsigned char str[256] = { 0 }; for (int i = 0; i < iniString.length(); ++i) { str[iniString[i]]++; } for (int i = 0; i < iniString.length(); ++i) { if (str[ iniString[i] ] > 1) return false; } return true; }*/ //方式二 /*bool CheckDifferent(string iniString) { sort(iniString.begin(),iniString.end()); if (unique(iniString.begin(),iniString.end()) == iniString.end() ) //去掉重复的元素，这里的去掉是将重复元素放在容器的末尾，伪去除，返回第一个重复的元素的迭代器，没有重复的元素返回end位置。 return true; return false; } */ //方式三 bool Qsort(string str,int low,int high) { if (low >= high) return true; int second = high; int first = low; int key = str[high]; while (low < high) { while (low < high && str[low] <= key) { low++; } swap(str[low],str[high]); while (low < high && str[high] >= key) { high--; } swap(str[low],str[high]); } if (low != first && str[low] == str[low-1]) return false; if(low != high && str[low == str[low+1]]) return false; return Qsort(str,first,low-1) && Qsort(str,low+1,second); } bool CheckDifferent(string iniString) { return Qsort(iniString,0,iniString.length()-1); } int main() { cout << CheckDifferent("aeiou") <<endl; cout << CheckDifferent("BarackObama") <<endl; cout << "hello..."<<endl; return 0; }