王道数据结构课后题目

2.2.3顺序表部分大题

#include <stdio.h>
#include <stdlib.h>

/*
6题
*/
int *solve_6(int *q1, int s1, int *q2, int s2) {
    int *ans = (int *) malloc((s1 + s2) * sizeof(int));
    int k1 = 0, k2 = 0, idx = 0;

    while(k1 < s1 && k2 < s2) {
        if(k1 < s1 && q1[k1] < q2[k2]) ans[idx ++] = q1[k1 ++];
        else if(k2 < s2 && q1[k1] >= q2[k2]) ans[idx ++] = q2[k2 ++];
    }

    if(idx == s1 + s2) return ans;

    if(k1 == s1)
        for(int i = k2; i < s2; i ++) ans[idx ++] = q2[i];
    else if(k2 == s2)
        for(int i = k1; i < s1; i ++) ans[idx ++] = q1[i];

    return ans;
}

/*
8题
*/
int solve_8(int *q, int s, int x) {
    int l = 0, r = s - 1, flag = 0;
    while(l < r) {
        int mid = l + r >> 1;
        if(q[mid] > x) r = mid;
        else if(q[mid] < x) l = mid + 1;
        else {
            if(mid == s - 1) break;

            int tmp = q[mid];
            q[mid] = q[mid + 1];
            q[mid + 1] = tmp;
            flag = 1;

            break;
        }
    }
    // printf("l: %d, r: %d\n", l, r);
    if(!flag) {
        for(int i = s; i > l; i --) q[i] = q[i - 1];
        q[l] = x;
        return 1;
    }

    return 0;
}

/*
11题:
1. 使用两个指针分别指向两个序列，然后指向元素值小的指针向后移动，counter++，直到counter == size(a) + size(b) >> 1 + 1;
2. 代码如下
3. 时间复杂度：o(s1 + s2), 空间复杂度：o(1)
*/
int solve_11(int *q1, int s1,int *q2, int s2) {
    int ans = -1;
    int stop = s1 + s2 >> 1;
    int counter = 0;
    int l1 = 0, l2 = 0;
    while(l1 < s1 && l2 < s2) {
        if(l1 < s1 && q1[l1] < q2[l2]) counter ++, ans = q1[l1], l1 ++;
        else if(l2 < s2 && q1[l1] >= q2[l2]) counter ++, ans = q2[l2], l2 ++;
        if(counter == stop) break;
    }
    return ans;
}

/*
12题:
1. 因为0 <= ai < n, 所以可以使用size为s的map数组存储每个元素出现的次数，然后再对map数组进行遍历找出次数大于 size/2 的元素进行返回即可
2. 代码如下
3. 时间复杂度：o(n), 空间复杂度：o(n)
*/
int solve_12(int *q, int s) {
    int map[s] = {0}, ans = -1;
    for(int i = 0; i < s; i ++)
        map[q[i]] ++;
    for(int i = 0; i < s; i ++) {
        if(map[i] > s / 2) {
            ans = map[i];
            break;
        }
    }
    return ans;
}

/*
1. 既然需要时间上尽可能高效，那就采用空间换时间的策略，定义足够大的数组来存储每个非负元素出现的次数，然后从下标从1开始遍历，遇到元素值为0的就输出
2. 代码如下：
3. 时间复杂度：o(n), 空间复杂度：o(n)
*/

int solve_13(int *q, int s) {
    int size = 1000010;
    int map[size] = {0};
    for(int i = 0; i < s; i ++)
        if(q[i] >= 0)
            map[q[i]] ++;
    for(int i = 1; i < size; i ++)
        if(!map[i])
            return i;
    return -1;
}

int main() {
    int q[] = {1, 2, 3};
    int ans = solve(q, 3);
    printf("%d ", ans);

    return 0;
}