顺序表在线OJ题（详解+图解）

ahao

发布于 2024-03-19 18:57:31

620

发布于 2024-03-19 18:57:31

文章被收录于专栏：学习学习

1：原地移除数组中所有的元素val（时间复杂度为O(N)空间复杂度为O(1)）

题目的大概意思是：用户自行输入一个数组，还要输入一个val的整形值，然后从数组中移除等于val的元素我们根据题目的要求，时间复杂度为O(N)空间复杂度为O(1) 可以用以下的办法：用一个for循环将数组遍历，再用if语句进行判断，如果不等于val的值，我们就将这个元素放入数组中，如果等于val的话i就继续+1，不放入数组中

代码实现如下：

int removeElement(int* nums, int numsSize, int val)
{
    int i = 0;
    int pos = 0;
    int ret=0;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[pos] = nums[i];
            pos++;
            ret++;
        }
    }
    return ret;
}

2：删除排序数组中的重复项

题目的要求是删除数组中的重复项，使其只出现一次，然后返回整个数组，并按照它们最初在 nums 中出现的顺序排列，并且输出数组的大小这题我们可以使用双指针的思路来解决：用while循环遍历，如果nums[src]!=nums[dst]，nums[1]（也就是nums[++dst]）就等于nums[src]，然后dst和src依次++，如果nums[src]=nums[dst]的话，src就直接++，dst不用++

代码实现如下：

int removeDuplicates(int* num, int numsSize)
{
    int src = 1;
    int dst = 0;
    while (src < numsSize)
    {
        if (num[src] != num[dst])
        {
            num[++dst] = num[src++];
        }
        else
            src++;
    }
    return dst + 1;//返回数组的大小
}

3：合并两个有序数组

本题是将两个有序的数组最后合并为一个有序数组，然后返回，我们可以先将数组nums2放入nums1中，然后再将nums1进行一次排序，然后返回nums1

代码实现如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//直接用qsort排序
    //int i = 0;
    //int pos = 0;
    //for (i = 0; i < n; i++)
    //{
    //    nums1[m + i] = nums2[pos++];
    //}
    //qsort(nums1, nums1Size, sizeof(int), cmp);
    //这种方法也比较简单,是将两个数组中末位的元素进行比较
    int end1 = m - 1;
    int end2 = n - 1;
    int i = m + n - 1;
    while (end1 >= 0 && end2 >= 0)
    {
        if (nums1[end1] >= nums2[end2])
        {
            nums1[i--] = nums1[end1--];
        }
        else
        {
            nums1[i--] = nums2[end2--];
        }
    }
    while (end2 >= 0)
    {
        nums1[i--] = nums2[end2--];
    }
}

4：旋转数组

这个题目算是很简单的，在我之前的文章中也讲解过，所以这里不做过多的解释了代码如下：大致的思路就是先将前k个元素旋转，然后旋转后一部分，然后再整体旋转

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

void reverse(int* nums, int start, int end) 
{
    while (start < end) 
    {
        swap(&nums[start], &nums[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(int* nums, int numsSize, int k) 
{
    k %= numsSize;
    if( k ==0 || numsSize == 1)
    {
        return;
    }
    
    //交换高到低
    reverse(nums, 0, k - 1);

    //交换低到高
    reverse(nums, k, numsSize - 1);

     //交换全部
    reverse(nums, 0, numsSize - 1);
}

5：数组形式的整数加法

本题的思路如下：我们的函数参数有num数组，就是我们输入的数组，numsize是num数组的元素个数，k是加上去的值，returnsize是最后加上k后的数组思考后我们就可以得出以下思路：

代码如下：

int* addToArrayForm(int* num, int numSize, int k, int* returnSize)
{
    int i=0;
    int sum=0;
    int x=pow(10,numSize-1);
    for(i=0;i<numSize;i++)
    {
        sum+=num[i]*x;
        x=x/10;
    }
    int SUM=sum+k;
    int count=0;
    while(SUM)
    {
        count++;
        SUM/=10;
    }
    int y=pow(10,count-1);
    for(i=0;i<count;i++)
    {
        returnSize[i]=(sum+k)/y;
        y/=10;
    }
    return returnSize;
}

好了，今天的分享到这里就结束了，感谢大家的支持！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历