常用算法

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);
    }
}