常用算法常用算法

1.字符串反转

void reverse(char *str){ char *p = str; char *q = str + strlen(str)-1; while(p > q){ char temp = *p; *p = *q; *q = temp; q--; p++; }

2.查找第一个只出现一次的字符

char findFirstChar(char *str){ char result = '\0'; int arr[256] = {0}; char *p = str; while (*p != '\0') { arr[*p]++; p++; } p = str; while (*p != '\0') { if (arr[*p] == 1) { return *p; } p++; } return result; }

【常用算法】3.求无序数组的中位数
相当于求解第k小的数，如果k为n/2或(n+1)/2的话，这就是我们要求的中位数.
我们可以通过快速排序来寻找中位数,时间复杂度为O(n),因为只需要获取中位数即可，所以使用二分法"思想的快速排序思想的变体，但是比快速排序的实现更快更简单，因为它只需要对牵涉范围的那些子数组排序。

int a[] = {12,4,3,67,900,22,28,9,61,53,23,12}; int n = sizeof(a) / sizeof(int); int m = n%2==0?n/2:(n+1)/2; //求解中位数 quick_select(a, m, 0, n-1); printf("the median nuber(%d-th): %d\n", m, a[m-1]); void quick_select(int *arr, int k, int leftIndex, int rightIndex){ if (k < leftIndex || k > rightIndex || leftIndex > rightIndex) { return; } int i = leftIndex; int j = rightIndex; int key = arr[i]; while (i < j) { if (i < j && arr[j] >= key) j--; if (i < j) { arr[i] = arr[j]; } if (i < j && arr[i] <= key) i++; if (i < j) { arr[j] = arr[i]; } } arr[i] = key; if (k <= i) { quick_select(arr, k, leftIndex, i-1); }else{ quick_select(arr, k, j+1, rightIndex); } }