【初阶数据结构与算法】顺序表与双指针算法详解

【初阶数据结构与算法】顺序表与双指针算法详解

引用

CSDN

1.

https://m.blog.csdn.net/hdxbufcbjuhg/article/details/143505937

本文将通过三个具体的LeetCode题目，讲解顺序表和双指针算法在处理数组问题中的应用。通过这些实例，读者可以更好地理解这两种方法的实现和优化过程。

顺序表练习

在顺序表练习中，我们会首先使用顺序表来解决，然后再介绍其它方法。在练习开始之前，需要说明的是，在实际开发中，我们通常不需要手写数据结构，因为现代编程语言（如C++的STL）中都有现成的数据结构可以使用。但在学习阶段，手写数据结构有助于加深理解。

在做题过程中，我们也会计算这些方法的时间复杂度和空间复杂度，也是对之前内容的一个复习。

1.移除数组中指定的元素

方法1（顺序表）

方法1的思路是直接使用顺序表。在顺序表中，我们提供了查找方法，并且提供了删除指定位置元素的方法。具体步骤如下：

1. 创建顺序表并初始化
2. 将数组中的内容尾插到顺序表
3. 使用循环查找要删除的元素，并将其删除
4. 将顺序表中的内容重新放入原数组

代码实现如下：

int removeElement(int* nums, int numsSize, int val) 
{
    int i = 0;
    SL sl;
    SLInit(&sl);
    for(i = 0; i<numsSize; i++)
    {
        SLPushBack(&sl,nums[i]);
    }
    while(SLFind(&sl,val) != -1)
    {
        int ret = SLFind(&sl,val);
        SLErase(&sl,ret);
    }
    for(i = 0; i<sl.size; i++)
    {
        nums[i] = sl.arr[i];
    }
    int k = sl.size;
    SLDestroy(&sl);
    return k;
}

这种方法的时间复杂度为O(N^2)，空间复杂度为O(N)。

方法2（双指针）

双指针算法的核心思想是使用两个指针（或下标）来处理数组。具体步骤如下：

1. 初始化两个指针src和dest，都指向数组的第一个元素
2. 遍历数组，如果src位置的值等于要删除的值，就直接让src往后走一步
3. 如果不等于，就把src位置的值赋给dest，随后让dest和src都往后走一步

代码实现如下：

int removeElement(int* nums, int numsSize, int val) 
{
    int src = 0;
    int dest = 0;
    while(src < numsSize)
    {
        if(nums[src] == val)
        {
            src++;
        }
        else
        {
            nums[dest++] = nums[src++];
        }
    }
    return dest;
}

这种方法的时间复杂度为O(N)，空间复杂度为O(1)。

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

方法1（顺序表）

方法1的思路与上一题类似，使用顺序表来处理数组。具体步骤如下：

1. 创建顺序表并初始化
2. 将数组中的内容尾插到顺序表
3. 使用循环查找重复元素并删除
4. 将顺序表中的内容重新放入原数组

代码实现如下：

int removeDuplicates(int* nums, int numsSize)
{
    SL sl;
    int i = 0;
    SLInit(&sl);
    for (i = 0; i < numsSize; i++)
    {
        SLPushBack(&sl, nums[i]);
    }
    for (i = 0; i < numsSize; i++)
    {
        if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1])
        {
            SLErase(&sl, i);
            numsSize--;
            i--;
        }
    }
    for (i = 0; i < numsSize; i++)
    {
        nums[i] = sl.arr[i];
    }
    SLDestroy(&sl);
    return numsSize;
}

这种方法的时间复杂度为O(N^2)，空间复杂度为O(N)。

方法2（双指针）

双指针算法的核心思想是使用两个指针（或下标）来处理数组。具体步骤如下：

1. 初始化两个指针src和dest，src指向第二个元素，dest指向第一个元素
2. 遍历数组，如果src位置的值等于dest位置的值，就直接让src往后走一步
3. 如果不等于，就让dest先++，再把src位置的元素赋值给dest位置的元素，最后让src++

代码实现如下：

int removeDuplicates(int* nums, int numsSize) 
{
    int src = 0, dest = 0;
    while(src < numsSize)
    {
       if(nums[src] == nums[dest])
          src++;
       else
          nums[++dest] = nums[src++];
    }
    return dest+1;    
}

这种方法的时间复杂度为O(N)，空间复杂度为O(1)。

3.双指针练习之合并两个有序数组

方法1（直接排序）

最简单的方法是将两个数组合并后直接排序。代码实现如下：

#include <stdlib.h>
int int_cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{ 
   for(int i = 0; i<n; i++)
   { 
      nums1[i+m] = nums2[i]; 
   }  
   qsort(nums1, m+n, sizeof(int), int_cmp);
}

这种方法的时间复杂度为O(N * logN)，空间复杂度为O(1)。

方法2（双指针）

双指针算法的核心思想是使用两个指针（或下标）来处理两个数组。具体步骤如下：

1. 初始化两个指针src1和src2，分别指向两个数组的有效元素的最后一个位置
2. 初始化dest指针，指向合并后数组的最后一个位置
3. 比较src1和src2指向的元素，将较大的元素放入dest位置，然后让dest、src1或src2减1
4. 如果src2还有剩余元素，将其全部移动到nums1中

代码实现如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int src1 = m-1;
    int src2 = n-1;
    int dest = m+n-1;
    while(src1>=0 && src2>=0)
    {
        if(nums1[src1] > nums2[src2])
        {
            nums1[dest--] = nums1[src1--];
        }
        else
        {
            nums1[dest--] = nums2[src2--];
        }
    }
     while(src2 >=0)
    {
        nums1[dest--] = nums2[src2--];
    }
}

这种方法的时间复杂度为O(N)，空间复杂度为O(1)。

通过这三个例子，我们可以看到双指针算法在处理数组问题时具有较高的效率。在实际开发中，合理选择和使用算法可以显著提高程序的性能。