用哈希算法的思想解决排序和字符串去重问题，时间复杂度为O(N)

 第一个题目：

int a[] = {12,13,12,13,19,18,15,12,15,16,17}，要求对数组a进行排序，要求时间复杂度为O(N) 

我们所知道的常规排序中，最优的解法也就是O(N*log2^N),那如何做到时间复杂度为O(N)呢？

运用哈希算法的思想就可以优化算法为O(N)

void Sort(int* a, int n) { assert(a); const int N = 20; int b[N] = { 0 }; for (int i = 0; i < n; i++) { int key = a[i]; ++b[key]; } int index = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < b[i]; j++) { a[index] = i; ++index; } } } int main() { int arr[] = { 12, 13, 12, 13, 19, 18, 15, 12, 15, 16, 17 }; int sz = sizeof(arr) / sizeof(arr[0]); Sort(arr, sz); for (int i = 0; i < sz; i++) { cout << arr[i] << " "; } cout << endl; cin.get(); return 0; }

第二道题

删除小写字母字符串中重复字符。如果可以，优先删除重复字符中排在比他小字符前面的字符。 比如，输入：bbcacdww；输出：bacdw 

暴力求解的效率太低，我们同样采用哈希算法的思想。

void DeleSame(char *a, int len) { bool b[256]; int key = 0; memset(b, 0, sizeof(b)); for (int i = 0; i < len; i++) { if (!b[a[i]]) { b[a[i]] = true; a[key++] = a[i]; } } a[key] = '\0'; } int main() { char arr[] = "ab111bcde332e"; int len = strlen(arr); DeleSame(arr, len); cout << arr << endl; system("pause"); return 0; }