LeetBook学习-C语言-数组

1.数组的操作

? ? ? ? 1.1?读取元素

? ? ? ? ? ? ? ? 知道内存地址可以快速访问，时间复杂度为O(1)

? ? ? ? 1.2?查找元素

? ? ? ? ? ? ? ? 从首地址开始，逐个查找，最坏时间复杂度为O(N)

? ? ? ? 1.3?插入元素

? ? ? ? ? ? ? ? 插入元素，首先位置要腾空，而后执行插入操作。

? ? ? ? 1.4?删除元素

? ? ? ? ? ? ? ? 删除掉某一个元素后，位置会出现空缺，后面的元素要进行填补操作。时间复杂度为O(N),N为数组的长度

2.相关例题（C语言代码）

? ? ? ? 2.1 给你一个整数数组?nums ，请计算数组的 中心下标 。

????????数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

????????如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

????????如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。（来源力扣（LeetCode）

int pivotIndex(int* nums, int numsSize) {
    int sum = 0;
    int temp = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }

    for (int i = 0; i < numsSize; i++) {
        if ( 2*temp== sum  - nums[i]) {
            return i;
        }
    
        temp += nums[i];
    }
    return -1;
}

????????2.2 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。（来源力扣（LeetCode） 使用二分法

? ? ? ? ? ? ? ? 因为是排序数组，二分法更方便。详解：以 0 1 2 3 4 5 6 为例 ????????

????????????????numsSize为7，left 为0，right为numsSize-1，而mid =left+(right-left)/2;逐渐二分

? ? ? ? ? ? ? ? 如果target小于mid的值，right=mid-1；

? ? ? ? ? ? ? ? 如果target大于mid的值，left=mid+1；? ? ? ? ?

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

? ? ? ? 2.3?以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回?一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间?。（来源力扣LeetCode）

int compare(const void* arg1, const void* arg2)
{
int** p1 = (int**)arg1;
int** p2 = (int**)arg2;

 if (**p1 > **p2) {
     return 1;
 } else if(**p1 < **p2) {
     return -1;
 } else {
     return 0;
 }
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){

if (intervals == NULL || intervalsSize == 0) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    return NULL;
}

qsort((void*)intervals, intervalsSize, sizeof(int**), compare);

int i, j;
int min, max;
int** pRet = NULL;
int* pTemp = NULL;
min = **intervals;
max = *(*intervals + 1);

pRet = (int**)malloc(sizeof(int*) * intervalsSize);
*returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize);
j = 0;
for (i = 1; i < intervalsSize; i++) {
    if (**(intervals + i) <= max) {
        if (*(*(intervals + i) + 1) > max) {
            max = *(*(intervals + i) + 1);
        }
    } else {
        pTemp = (int*)malloc(sizeof(int) * 2);
        pTemp[0] = min;
        pTemp[1] = max;
        pRet[j] = pTemp;
        *(*returnColumnSizes + j) = 2;
        j++;
        min = **(intervals + i);
        max = *(*(intervals + i) + 1);
    }
}
pTemp = (int*)malloc(sizeof(int) * 2);
pTemp[0] = min;
pTemp[1] = max;
pRet[j] = pTemp;
*(*returnColumnSizes + j) = 2;
*returnSize = j + 1;
return pRet;
}