首页 > 编程语言 >【数据结构-数组】数组的相关算法

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

时间：2022-10-30 21:22:06浏览次数：54  
标签：int 元素 ++ 算法 low 数组 数据结构 指针

目录

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;
}

5.3 求多数元素——摩尔投票法

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/2 ⌋ 次的元素。

（略）

标签：int,元素,++,算法,low,数组,数据结构,指针
From： https://www.cnblogs.com/Mount256/p/16842283.html

相关文章

  • 基于鲸鱼优化算法的5G信道估计（Matlab代码实现）
    ......
  • 基于改进人工蜂群算法的K均值聚类算法（Matlab代码实现）
    ......
  • 实验一：决策树算法实验
    实验一：决策树算法实验【实验目的】理解决策树算法原理，掌握决策树算法框架；理解决策树学习算法的特征选择、树的生成和树的剪枝；能根据不同的数据类型，选择不同的决策树算......
  • 决策树算法实验
    一、【实验目的】理解决策树算法原理，掌握决策树算法框架；理解决策树学习算法的特征选择、树的生成和树的剪枝；能根据不同的数据类型，选择不同的决策树算法；针对特定应用场景......
  • 实验一：决策树算法实验
    一、【实验目的】理解决策树算法原理，掌握决策树算法框架；理解决策树学习算法的特征选择、树的生成和树的剪枝；能根据不同的数据类型，选择不同的决策树算法；针对特定应用场......
  • 数组2
    冒泡算法voidbubble_sort(intarr[],intsz)//void为了排序完后不返回{inti=0;for(i=0;i<sz-1;i++){//intj=0;for(j=0;j<sz-1-......
  • 决策树算法实验
    决策树算法实验 【实验目的】1、理解决策树算法原理，掌握决策树算法框架；2、理解决策树学习算法的特征选择、树的生成和树的剪枝；3、能根据不同的数据类型，选择不同的......
  • 贝叶斯分类算法及其概率论基础
    理论基础：1.先验概率：先验概率（priorprobability）是指根据以往经验和分析得到的概率（典型的例子是概率论中应用题的已知条件），如全概率公式，它往往作为"由因求果"问题中的"因"出现......
  • 排序算法之最长和谐子序列
    题目和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在，给你一个整数数组nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。数组的子序列是......
  • 算法数组之种花问题
    题目假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组  flowerbed表示花坛，由若干0......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99