[数据结构与算法] 【数据结构-数组】数组的相关算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构-数组】数组的相关算法 -> 正文阅读

[数据结构与算法]【数据结构-数组】数组的相关算法

文章目录

1 无序数组的排序——快速排序

1.1 升序排序

一趟排序的思路：

选取区间 A 最左边的元素 x 作为基准值；
从区间 A 的最右边开始，往左找，碰到第一个比 x 小的元素时停下，把下标记为 j；（基准数在最左边，必须从最右边开始扫描！）
从区间 A 的最左边开始，往右找，碰到第一个比 x 大的元素时停下，把下标记为 i；
交换 A[i] 和 A[j]；
继续从 j 往左找，再从 i 往右找，重复上述过程，直到 i 和 j 碰面为止，将 A[i] 与第一个元素 x 交换；
将区间 A 分为两段：[最左边, i-1]，[i+1, 最右边]（或[最左边, j-1]，[j+1, 最右边]），重复上述过程。

void QSort (int A[], int low, int high){
    if (low >= high)
        return;

    int i = low, j = high; // 左右指针分别指向区间两端
    int pivot; // 基准值
    
    将 A 数组中随机一个元素和 A[low] 交换; // 随机选取基准值
    pivot = A[low]; // 最左边作为基准值
    
    while (i != j){
        while ((i < j) && (A[j] > pivot)) // 右指针从区间右端往左端移动
            j--;
        while ((i < j) && (A[i] <= pivot)) // 左指针从区间左端往右端移动（注意还有等于条件）
            i++;
        if (i < j)
            swap(A[i], A[j]); // 交换 A[i] 和 A[j]
    }
    
    swap(A[low], A[i]); // 将基准值放入最终位置
    QSort(A, low, i-1); // 递归处理左区间
    QSort(A, i+1, high);  // 递归处理右区间
}

1.2 降序排序

一趟排序的思路：

选取区间 A 最左边的元素 x 作为基准值；
从区间 A 的最右边开始，往左找，碰到第一个比 x 大的元素时停下，把下标记为 j；（基准数在最左边，必须从最右边开始扫描！）
从区间 A 的最左边开始，往右找，碰到第一个比 x 小的元素时停下，把下标记为 i；
交换 A[i] 和 A[j]；
继续从 j 往左找，再从 i 往右找，重复上述过程，直到 i 和 j 碰面为止，将 A[i] 与第一个元素 x 交换；
将区间 A 分为两段：[最左边, i-1]，[i+1, 最右边]（或[最左边, j-1]，[j+1, 最右边]），重复上述过程。

void QSort (int A[], int low, int high){
    if (low >= high)
        return;

    int i = low, j = high; // 左右指针分别指向区间两端
    int pivot; // 基准值
    
    将 A 数组中随机一个元素和 A[low] 交换; // 随机选取基准值
    pivot = A[low]; // 最左边作为基准值
    
    while (i != j){
        while ((i < j) && (A[j] <= pivot)) // 右指针从区间右端往左端移动
            j--;
        while ((i < j) && (A[i] >= pivot)) // 左指针从区间左端往右端移动
            i++;
        if (i < j)
            swap(A[i], A[j]); // 交换 A[i] 和 A[j]
    }
    
    swap(A[low], A[i]); // 将基准值放入最终位置
    QSort(A, low, i-1); // 递归处理左半区间
    QSort(A, i+1, high);  // 递归处理右半区间
}

2 有序数组的查找——折半查找（二分查找）

2.1 升序数组的查找

左闭右闭写法（[low, high]，推荐）：

// A：数组，low 和 high：数组区间左端点及右端点下标/索引，x：数组元素
int Search(int A[], int low, int high, int x){
    int mid;
    while (low <= high){ // 左闭右闭
        mid = low + (high - low) / 2;
        if (A[mid] > x) // 若中间值大于 x，说明 x 在左半段
            high = mid - 1;
        else if (A[mid] < x) // 若中间值小于 x，说明 x 在右半段
            low = mid + 1;
        else // 若中间值就是 x
            return mid;
    }
    return -1; // 查找失败
}

左闭右开写法（[low, high)，high 对应的数组元素搜索不到）：

// A：数组，low 和 high：数组区间左端点及右端点下标/索引，x：数组元素
int Search(int A[], int low, int high, int x){
    int mid;
    while (low < high){ // 左闭右开，high 对应的数组元素搜索不到
        mid = low + (high - low) / 2;
        if (A[mid] > x) // 若中间值大于 x，说明 x 在左半段
            high = mid; // high 对应的数组元素搜索不到，即 [low, mid)
        else if (A[mid] < x) // 若中间值小于 x，说明 x 在右半段
            low = mid + 1;
        else // 若中间值就是 x
            return mid;
    }
    return -1; // 查找失败
}

2.2 降序数组的查找

左闭右闭写法（[low, high]，推荐）：

// A：数组，low 和 high：数组区间左端点及右端点下标/索引，x：数组元素
int Search(int A[], int low, int high, int x){
    int mid;
    while (low <= high){ // 左闭右闭
        mid = low + (high - low) / 2;
        if (A[mid] < x) // 若中间值小于 x，说明 x 在左半段
            high = mid - 1;
        else if (A[mid] > x) // 若中间值大于 x，说明 x 在右半段
            low = mid + 1;
        else // 若中间值就是 x
            return mid;
    }
    return -1; // 查找失败
}

左闭右开写法（[low, high)，high 对应的数组元素搜索不到）：

// A：数组，low 和 high：数组区间左端点及右端点下标/索引，x：数组元素
int Search(int A[], int low, int high, int x){
    int mid;
    while (low < high){ // 左闭右开，high 对应的数组元素搜索不到
        mid = low + (high - low) / 2;
        if (A[mid] < x) // 若中间值小于 x，说明 x 在左半段
            high = mid; // high 对应的数组元素搜索不到，即 [low, mid)
        else if (A[mid] > x) // 若中间值大于 x，说明 x 在右半段
            low = mid + 1;
        else // 若中间值就是 x
            return mid;
    }
    return -1; // 查找失败
}

3 有序数组的合并——归并思想

3.1 归并两个升序数组

int C[n+m]; // 全局新数组

// 数组 A 及其长度 n，数组 B 及其长度 m
void UpMerge (int A[], int n, int B[], int m){
    int i = j = 0; // i，j 指针指向数组 A 和 B
    int k = 0;     // k 指针指向数组 C
    
    while ((i < n) && (j < m)){  // 当有一个数组遍历完时，退出循环
        if (A[i] < B[j]){ // 较小者先进入新数组
            C[k] = A[i];
            i++;
        }
        else{
            C[k] = B[j];
            j++;
        }
        k++;
    }
    
    // 剩余元素直接进入新数组
    for (; i < n; i++, k++)
        C[k] = A[i];
    for (; j < m; j++, k++)
        C[k] = B[j];
}

3.2 归并两个降序数组

int C[n+m]; // 全局新数组

// 数组 A 及其长度 n，数组 B 及其长度 m
void DownMerge (int A[], int n, int B[], int m){
    int i = j = 0; // i，j 指针指向数组 A 和 B
    int k = 0;     // k 指针指向数组 C
    
    while ((i < n) && (j < m)){  // 当有一个数组遍历完时，退出循环
        if (A[i] > B[j]){ // 较大者先进入新数组
            C[k] = A[i];
            i++;
        }
        else{
            C[k] = B[j];
            j++;
        }
        k++;
    }
    
    // 剩余元素直接进入新数组
    for (; i < n; i++, k++)
        C[k] = A[i];
    for (; j < m; j++, k++)
        C[k] = B[j];
}

3.3 升序和降序归并为升序

int C[n+m]; // 全局新数组

// 升序数组 A 及其长度 n，降序数组 B 及其长度 m
void UpMerge (int A[], int n, int B[], int m){
    int i = 0; // i 指针指向数组 A
    int j = m; // j 指针指向数组 B
    int k = 0; // k 指针指向数组 C
    
    while ((i < n) && (j > 0)){  // 当有一个数组遍历完时，退出循环
        if (A[i] > B[j]){ // 较小者先进入新数组
            C[k] = A[i];
            i++;
        }
        else{
            C[k] = B[j];
            j--;
        }
        k++;
    }
    
    // 剩余元素直接进入新数组
    for (; i < n; i++, k++)
        C[k] = A[i];
    for (; j = 0; j--, k++)
        C[k] = B[j];
}

3.4 升序和降序归并为降序

int C[n+m]; // 全局新数组

// 升序数组 A 及其长度 n，降序数组 B 及其长度 m
void DownMerge (int A[], int n, int B[], int m){
    int i = n; // i 指针指向数组 A
    int j = 0; // j 指针指向数组 B
    int k = 0; // k 指针指向数组 C
    
    while ((i > 0) && (j < m)){  // 当有一个数组遍历完时，退出循环
        if (A[i] > B[j]){ // 较大者先进入新数组
            C[k] = A[i];
            i--;
        }
        else{
            C[k] = B[j];
            j++;
        }
        k++;
    }
    
    // 剩余元素直接进入新数组
    for (; i = 0; i--, k++)
        C[k] = A[i];
    for (; j < m; j++, k++)
        C[k] = B[j];
}

4 数组元素的删除——快慢指针

快指针：正常遍历数组元素
慢指针：遇到多少个满足条件的元素就滞后于快指针多少个位置，同时能记录删除后需要保存的元素个数

4.1 删除特定元素

4.1.1 无序表中删除所有值为 x 的元素

从线性表中删除所有其值为 x 的元素，要求时间复杂度为 O(n)，空间复杂度为 O(1)。

解法一（推荐）：

void Delete_x (int A[], int x){
    int i; // 快指针，正常遍历数组元素
    int j; // 慢指针，遇到多少个值为 x 的元素就滞后于快指针多少个位置，即需要保存的元素个数
    
    for (i = 0, j = 0; i < length; i++){ // 快指针，正常遍历数组元素
        if (A[i] != x){     // 如果不是值为 x 的元素
            A[j] = A[i];    // 当前元素往前移 i-j 个位置，即移到下标为 j 的位置
            j++;            // 慢指针 + 1
        }
        // 如果是值为 x 的元素，则慢指针 j 不加 1，这样就和快指针 i 多滞后了一个位置
        // 此时 j 指向值为 x 的元素
    }
    
    length = j;
}

解法二：

void Delete_x (int A[], int x){
    int i; // 快指针，正常遍历数组元素
    int j; // 慢指针，遇到多少个值不为 x 的元素就滞后于快指针多少个位置
    
    for (i = 0, j = 0; i < length; i++){
        if (A[i] == x)  // 如果是值为 x 的元素
            j++;        // 慢指针 + 1
        else            // 如果不是值为 x 的元素
            A[i-j] = A[i];  // 当前元素往前移 j 个位置，即移到下标为 i-j 的位置
    }
    
    length = length - j;
}

4.1.2 有序表中删除所有值为 x 的元素

从有序表中删除所有其值为 x 的元素。

void Delete_x (int A[], int x){
    int i = 0; // 头指针
    int j = length - 1; // 尾指针
    
    while ((A[i] != x) && (i < length)) // 从表头开始往右找第一个值等于 x 的元素
        i++;
    while ((A[j] != x) && (j >= 0)) // 从表尾开始往左找第一个值小于等于 t 的元素
        j--;
    
    int d = j - i + 1;
    for (; j < length; j++) // 将元素前移
        L.data[j - d] = L.data[j];
        
    length = length - d;
}

4.2 删除值为 s 到 t 之间的所有元素

4.2.1 无序表中删除值为 s 到 t 之间的所有元素

从顺序表中删除其值为 s 到 t 之间的所有元素。

解法一（推荐）：

void Delete_s_t (int A[], int s, int t){
    int i; // 快指针，正常遍历数组元素
    int j; // 慢指针，遇到多少个值为 s 到 t 之间的元素就滞后于快指针多少个位置，即需要保存的元素个数
    
    for (i = 0, j = 0; i < length; i++){    // 快指针，正常遍历数组元素
        if ((A[i] < s) || (A[i] > t)){      // 如果不是 s 到 t 之间的元素
            A[j] = A[i];    // 当前元素往前移 i-j 个位置，即移到下标为 j 的位置
            j++;            // 慢指针 + 1
        }
        // 如果是 s 到 t 之间的元素，则慢指针 j 不加 1，这样就和快指针 i 多滞后了一个位置
        // 此时 j 指向值为 x 的元素
    }
    
    length = j;
}

解法二：

void Delete_x (int A[], int x){
    int i; // 快指针，正常遍历数组元素
    int j; // 慢指针，遇到多少个值不为 s 到 t 之间的元素就滞后于快指针多少个位置
    
    for (i = 0, j = 0; i < length; i++){
        if ((s <= A[i]) && (A[i] <= t))  // 如果是值为 s 到 t 之间的元素
            j++;        // 慢指针 + 1
        else            // 如果不是值为 s 到 t 之间的元素
            A[i-j] = A[i];  // 当前元素往前移 j 个位置，即移到下标为 i-j 的位置
    }
    
    length = length - j;
}

4.2.2 有序表中删除值为 s 到 t 之间的所有元素

从有序表中删除其值为 s 到 t 之间的所有元素。

void Delete_s_t (int A[], int s, int t){
    int i = 0; // 头指针
    int j = length - 1; // 尾指针
    
    while ((A[i] < s) && (i < length)) // 从表头开始往右找第一个值大于等于 s 的元素
        i++;
    while ((A[j] > t) && (j >= 0)) // 从表尾开始往左找第一个值小于等于 t 的元素
        j--;
    
    int d = j - i + 1;
    for (; j < length; j++) // 将元素前移
        L.data[j - d] = L.data[j];
        
    length = length - d;
}

4.3 删除重复元素

4.3.1 有序表中删除所有重复的元素

从有序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

解法一（推荐）：

void Delete_Same (int A[]){
    int i; // 快指针，正常遍历数组元素，初始指向第 1 个元素
    int j; // 慢指针，遇到多少个重复元素就滞后于快指针多少个位置，即需要保存的元素个数，初始指向第 0 个元素
    
    for (i = 1, j = 0; i < length; i++){ // 快指针，正常遍历数组元素
        if (A[i] != A[j]){  // 如果当前元素和下标为 j 的元素不相等
            j++;            // 慢指针 + 1
            A[j] = A[i];    // 当前元素往前移 i-j 个位置，即移到下标为 j 的位置
        }
        // 如果当前元素和下标为 j 的元素相等，则慢指针 j 不加 1，这样就和快指针 i 多滞后了一个位置
        // 此时 j 指向重复元素组的第一个元素
    }
    
    length = j + 1;
}

解法二：

void Delete_Same (int A[]){
    int prev = A[0]; // 记录前一个元素，初始值为 A[0]
    int i; // 快指针，正常遍历数组元素
    int j; // 慢指针，遇到多少个重复元素就滞后于快指针多少个位置，即需要保存的元素个数
    
    for (i = 1, j = 1; i < length; i++){ // 快指针，正常遍历数组元素
        if (A[i] != prev){  // 如果当前元素和前一个元素不重复
            prev = A[i];    // 更新记录前一个元素
            A[j] = A[i];    // 当前元素往前移 j 个位置
            j++;            // 慢指针 + 1
        }
        // 如果当前元素和前一个元素重复，则慢指针 j 不加 1，这样就和快指针 i 多滞后了一个位置
        // 此时 j 指向重复元素组的第一个元素
    }
    
    length = j;
}

4.3.2 无序表中删除所有重复的元素

从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

解法：若要使时间复杂度为 O(n)，则需使用散列表。

（略）

5 数组的相关算法杂例

5.1 数组逆置

// 数组 A，区间左端点下标 low，区间右端点下标 high
void Reverse (int A[], int low, int high){
    for (int i = low; i <= low + (high - low) / 2; i++)
        swap(A[i], A[high - i]); // 交换头尾元素
}

5.2 求数组的最大和最小元素

#define INT_MAX 0x7FFFFFFF // int 型最大值

// 求最小元素
// 数组 A，区间左端点下标 low，区间右端点下标 high
int Min (int A[], int low, int high){
    int A_Min = INT_MAX;
    for (int i = low; i <= high; i++){
        if (A[i] < D_Min)
            A_Min = A[i];
    }
    return A_Min;
}

#define INT_MIN 0x80000000 // int 型最小值

// 求最大元素
// 数组 A，区间左端点下标 low，区间右端点下标 high
int Max (int A[], int low, int high){
    int A_Max = INT_MIN;
    for (int i = low; i <= high; i++){
        if (A[i] > D_Max)
            A_Max = A[i];
    }
    return A_Max;
}