2018-408算法题

题目

找出数组中未出现的最小正整数

思想

建立长度为 n 的辅助数组A，值全为0。
遍历原数组，出现不超过数组长度的正整数 x，将 A[x-1] 改为 1。
遍历数组 A， 第一个为 0 元素 A[i], i+1 为所求值。若都为 1，则长度加一为所求值

代码

int find(int B[], int len) {
    int *A;
    A = (int *)malloc(sizeof(int)*len);
    memset(A, 0, sizeof(int)*len);

    for (int k = 0; k < len; k++) {
        if (B[k] > 0 && B[k] <= len) {
            A[B[k] - 1] = 1;
        }
            
    }
    for (int i = 0; i < len; i++) {
        if (A[i] == 0) return i+1;
    } 
    return len+1;
}

测试

int main() {
    int B1[] = {-5, 3, 2, 3};
    int B2[] = {1, 2, 3, 4};
    printf("find(B1): %d \n", find(B1, 4));
    printf("find(B2): %d \n", find(B2, 4));
    return 0;
}

捕获5.PNG