数据结构第四弹---数组相关OJ题

简介: 数据结构第四弹---数组相关OJ题


1、移除元素

1.1、题目描述

移除元素

1.2、思路讲解

思路一:(时间复杂度O(N^2)

如果数组元素等于val,则将后面的元素往前挪动一个位置。

思路二:(空间复杂度O(N)不符合题目要求)

用空间换时间,将不等于val的值赋值到新的数组,然后将新的数组赋值给原数组。

思路三:(时间复杂度O(N))

用双指针,一个指针(src)用来遍历数组,一个指针(dest)用来遍历有效数据,遍历一遍数组,如果该值等于val,那么src++,如果该值不等于val,将src位置的元素赋值到dest位置,然后src++,dest++,因为dest是后置++,先使用再+1,因此dest就是有效数据个数。

1.3、画图分析

下图为思路三的画图分析喔,想了解其他思路的分析私信博主喔!

1.4、代码实现

思路三

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

此处只需返回不等于val值的个数,因此可以少去等于val的判断,代码实现如下。

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

2、删除有序数组

2.1、题目描述

删除有序数组

2.2、思路讲解

思路一:(时间复杂度O(N^2)空间复杂度O(1))

遍历数组,如果前面一个数等于后面一个数,将后面的所有元素向前移动一个位置。但是最后一个需要特殊处理,因为最后一个位置没有元素与之相比,处理的方式就是直接将最后一个数据放入有序数组的最后一个即可。

思路二:(时间复杂度O(N)空间复杂度O(N))

用空间换时间,将前后的数据进行比较,前后不相等则放入新数组中,同样需要处理最后一个数据,处理的方式是直接将最后一个数据放入有序数组的最后一个即可。

思路三:(时间复杂度O(N)空间复杂度O(1))

使用双指针,一个指针(src)用来遍历数组,一个指针(dest)用来记录有效数据,如果前后不相等则将元素放入下标dest中,然后src++,dest++,如果相等则src++。

2.3、画图分析

思路三

2.4、代码实现

思路一

int removeDuplicates(int* nums, int numsSize) 
{
    for(int i=0;i<numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[i]==nums[j])
            {
                for(int k=j;k<numsSize-1;k++)
                {
                    nums[k]=nums[k+1];
                }
                j--;
                numsSize--;
            }
        }
    }
    return numsSize;
}

思路三

int removeDuplicates(int* nums, int numsSize) 
{
     int dest=0;
     int src=0;
     while(src<numsSize-1)
     {
         if(nums[src]!=nums[src+1])
         {
             nums[dest]=nums[src];
             dest++;
             src++;
         }
         else
         {
               src++;
         }
     }    
     nums[dest++]=nums[src];//最后一个元素的处理
     return dest;
}

3、合并两个有序数组

3.1、题目描述

合并两个有序数组

3.2、思路讲解

思路一:(时间复杂度O(m+n)空间复杂度O(m+n)

开辟一个新的数组,大小为m+n(使用变长数组),比较两个数组的数值,哪个小则依次放入新的数组中,最后把新的数组的值赋值到nums1中。

C99标准中,新增了可变长度数组。在leetcode,牛客等刷题网站可以使用变长数组,但是VS不支持。
变长数组中的“变”不是指可以修改已创建数组的大小,一旦创建了变长数组,它的大小则保持不变。这里的“变”指的是:在创建数组时,可以使用变量指定数组的长度。(普通数组只能用常量或常量表达式指定数组的长度)

思路二:

从两个数组的末尾比较数值,大的值放入nums1的最后一个,依次类推,(前提是有序数组)。需要注意nums2是否赋值完,nums2赋值完不需要加判断,没有赋值完则需要加判断。

3.3、画图分析

思路二

3.4、代码实现

思路二

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
  int end1 = m-1;
  int end2 = n-1;
  int end = m + n - 1;
  while (end1 >= 0 && end2 >= 0)
  {
    if (nums1[end1] > nums2[end2])
    {
      nums1[end] = nums1[end1];
      end--;
      end1--;
    }
    else
    {
      nums1[end] = nums2[end2];
      end--;
      end2--;
    }
  }
  while (end2 >= 0)//nums2还剩数值
  {
    nums1[end] = nums2[end2];
    end--;
    end2--;
  }
}

总结

本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

相关文章
|
1月前
|
存储 Java 程序员
数据结构之 - 深入了解数组数据结构
数据结构之 - 深入了解数组数据结构
38 6
|
1月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
99 64
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
25 7
|
1月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
20 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
4月前
【数据结构OJ题】环形链表
力扣题目——环形链表
37 3
【数据结构OJ题】环形链表
|
4月前
|
存储 索引
【数据结构OJ题】设计循环队列
力扣题目——设计循环队列
34 1
【数据结构OJ题】设计循环队列
|
4月前
【数据结构OJ题】有效的括号
力扣题目——有效的括号
36 1
【数据结构OJ题】有效的括号
|
4月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
51 1
【数据结构OJ题】复制带随机指针的链表

热门文章

最新文章