顺序表——习题

1. 轮转数组

代码实现：

// 逆置数组
void nizhi_array(int *nums, int l, int r) { // 左闭右闭
    if (l >= r) {
        return ;
    }
    for (int i = l, j = r; i < j; i++, j--) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

void rotate(int *nums, int numsSize, int k) {
    if (nums == NULL || k == 0 || numsSize == 1) {
        return ;
    }
    if (k > numsSize) {
        k %= numsSize;
    }
    nizhi_array(nums, 0, numsSize - 1);
    nizhi_array(nums, 0, k - 1);
    nizhi_array(nums, k, numsSize - 1);
}

2. 合并两个有序数组

代码实现：把数组nums2元素添加在数组nums1元素后面，再冒泡排序

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int k = m;
    for (int i = 0; i < n; i++) {
        nums1[k++] = nums2[i];
    }
    int flag = 1; // 标志位优化 当序列在找到所有的最大值之前就已经将序列排好序了，直接结束循环
    for (int i = nums1Size - 1; i >= 1 && flag; i--) { // i决定了哪一轮冒泡
        flag = 0;
        for (int j = 0; j < i; j++) { // j决定哪两个元素进行比较
            if (nums1[j] > nums1[j + 1]) {
                flag = 1;
                int temp = nums1[j];
                nums1[j] = nums1[j + 1];
                nums1[j + 1] = temp;
            }
        }
    }
}

3. 移动零

代码实现：双指针

void moveZeroes(int *nums, int numsSize){
    int l = 0; // 指向零
    int r = 0; // 不指向零
    while (r < numsSize) {
        if (nums[r] != 0) {
            int temp = nums[r];
            nums[r] = nums[l];
            nums[l] = temp;
            l++;
        }
        r++;
    }
}

4. 复写零

代码实现：

void duplicateZeros(int *arr, int arrSize) {
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] == 0) {
            for (int j = arrSize - 1; j > i + 1; j--) {
                arr[j] = arr[j - 1];
            }
            if (i < arrSize - 1) {
                arr[i + 1] = 0;
            } 
            i += 1;
        }
    }
}

5. 删除有序数组中的重复项

代码实现：

int removeDuplicates(int* nums, int numsSize){
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] == nums[i - 1]) {
            for (int j = i; j < numsSize -1; j++) {
                nums[j] = nums[j + 1];
            }
            i--;
            numsSize--;
        }
    }
    return numsSize;
}

6. 颜色分类

代码实现：

（1）单指针

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void sortColors(int *nums, int numsSize) {
    int ptr = 0;
    for (int i = 0; i < numsSize; ++i) { // 先将数组中的0排好
        if (nums[i] == 0) {
            swap(&nums[i], &nums[ptr]);
            ++ptr;
        }
    }
    for (int i = ptr; i < numsSize; ++i) { // 再将数组中的1排在0后面，剩下的全部都是2
        if (nums[i] == 1) {
            swap(&nums[i], &nums[ptr]);
            ++ptr;
        }
    }
}

（2）双指针

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void sortColors(int *nums, int numsSize) {
    int p0 = 0, p1 = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] == 1) {
            swap(&nums[i], &nums[p1]);
            ++p1;
        } else if (nums[i] == 0) {
            swap(&nums[i], &nums[p0]);
            if (p0 < p1) {
                swap(&nums[i], &nums[p1]);
            }
            ++p0;
            ++p1;
        }
    }
}

7. 加一

代码实现：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int *digits, int digitsSize, int *returnSize) {
    for (int i = digitsSize - 1; i >= 0; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
        } else {
            digits[i]++;
            *returnSize = digitsSize;
            return digits;
       }
   }
    *returnSize = digitsSize + 1;
    int *ret = (int*)malloc(sizeof(int) * (digitsSize + 1));
    memset(ret, 0, sizeof(int) * (digitsSize + 1));
    ret[0] = 1;
    return ret;
}

8. 多数元素

代码实现：投票法
因为多数元素在数组里出现的次数绝对大于n/2，所以用其他元素消去多数元素，剩下的必然是多数元素（两两抵消）

int majorityElement(int *nums, int numsSize){
    int a = nums[0]; // 投票对象
    int flag = 1; // 票数
    for (int i = 1; i < numsSize; i++) { // 遍历投票对象
        if (a == nums[i]) { // 投票对象相同，票数+1
            flag++;
        } else { // 投票对象不同，票数-1
            flag--;
            if (flag < 0) { // 该元素不是多数元素，更新投票对象并把票数置1
                a = nums[i];
                flag = 1;
            }
        }
    }
    return a; 
}

9. 丢失的数字

代码实现：计数排序思想

int missingNumber(int *nums, int numsSize) {
    int arr[numsSize + 1];
    memset(arr, 0, sizeof(arr));
    int i;
    for (i = 0; i < numsSize; i++) {
        arr[nums[i]]++;
    }
    for (i = 0; i <= numsSize; i++) {
        if (arr[i] == 0) {
            break;
        }
    }
    return i;
}