C语言移除元素的三种思路讲解

目录
  • 问题描述
  • 解题方案
    • 思路一
    • 思路二
    • 思路三(最优解)

问题描述

原题链接：https://leetcode.cn/problems/remove-element/

解题方案

思路一

思路一：

首先通过简单分析，很明显这是一道顺序表相关问题。首先能够想到的是暴力求解，即思路一：找到所有的val，每次挪动val后的数据覆盖删除val。

代码展示：

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

但是对于思路一，空间复杂度显然是O(1)，当我们计算时间复杂度的时候，最坏的情况是数组中大部分值都为val，这时时间复杂度近似为O(1+2+……+n-1)即O(n^2)，显然O(n^2)的时间复杂度还是不尽人意，本着降低时间复杂度，我们可以怎样优化呢？

思路二

思路二：

在创建一个临时数组tmp，遍历nums数组，把不是val的数值放到tmp数组，最后把tmp数组的内容依次拷贝到nums数组，返回tmp数组长度。

代码展示：

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

注释：这里的特殊处理是因为在函数中使用了变长数组 int tmp[numsSize];而变长数组的大小不能为0，这是使用特殊处理，是因为力扣的测试用例中含有[] 0。

对于思路二，最坏的情况我们只遍历了1遍数组，即时间复杂度为O(n)，但是这明显是一种用空间换区时间的方法，在此过程我们创建了numsSize个变量，即空间复杂度为O(n)。所以我们能不能通过再降低空间复杂度，进一步优化呢？

思路三(最优解)

思路三：

创建两个变量src、dest，初始时指向首部，判断nums[src]是否等于val，如果等于val则dest指向不动，src向后偏移，直到nums[src]!=val，令nums[dest]=nums[src]，然后src、dest都向后偏移，直到src遍历完数组，程序结束。

代码展示：

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

这种思路下时间复杂度为遍历整个数组O(n)，创建的变量为有限个，所以空间复杂度为O(1)。相比之下为最优解。

到此这篇关于C语言移除元素的三种思路讲解的文章就介绍到这了,更多相关C语言移除元素内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数组添加和删除元素的实现

    数组不擅长插入(添加)和删除元素.数组的优点在于它是连续的,所以查找数据速度很快.但这也是它的一个缺点.正因为它是连续的,所以当插入一个元素时,插入点后所有的元素全部都要向后移:而删除一个元素时,删除点后所有的元素全部都要向前移. 插入算法 # include <stdio.h> int main(void) { int a[23] = {1, 5, 66, 8, 55, 9, 1, 32, 5, 65, 4, 8, 5, 15, 64, 156, 1564, 15, 1, 8, 9, 7,

  • C语言基础双指针移除元素解法

    C语言基础双指针移除元素解法

    本题方法:双指针.知识比较基础,思路简单 题目: 我的题解: int removeElement(int* nums, int numsSize, int val) { int i=0,j=0; int cnt=0; //计数器,用来统计val的个数 while(j<numsSize) { if(nums[j]!=val) //1 { nums[i]=nums[j]; i++; j++; } else //2 { j++; cnt++; } } return numsSize-cnt; //3

  • C语言移除元素的三种思路讲解

    目录 问题描述 解题方案 思路一 思路二 思路三(最优解) 问题描述 原题链接:https://leetcode.cn/problems/remove-element/ 解题方案 思路一 思路一: 首先通过简单分析,很明显这是一道顺序表相关问题.首先能够想到的是暴力求解,即思路一:找到所有的val,每次挪动val后的数据覆盖删除val. 代码展示: int find(int*nums,int numsSize,int val) { int i=0; for(i=0;i<numsSize;i++)

  • C语言中函数指针的三种使用方法总结

     C语言中函数指针的三种使用方法总结 在这里分享一下自己的心得,希望和大家一起分享技术,如果有什么不足,还请大家指正.写出这篇目的,就是希望大家一起成长,我也相信技术之间没有高低,只有互补,只有分享,才能使彼此更加成长. 定义方式:int (*p)(int x, int y); 实现代码: #include <stdio.h> int sum(int x, int y){ return x + y; } int reduce(int x, int y){ return x - y; } int

  • JS中动态创建元素的三种方法总结(推荐)

    JS中动态创建元素的三种方法总结(推荐)

    1.动态创建元素一 document.write() 例如向页面中输出一个 li 标签 <pre class="html" name="code"><span style="font-size:12px;"><script> document.write("<li>123</li>"); </script></span> body标签中就会插入

  • Python 删除List元素的三种方法remove、pop、del

    1.remove: 删除单个元素,删除首个符合条件的元素,按值删除,从左向右依次删除符合条件的值 举例说明: >>> str=[1,2,3,4,5,2,6] >>> str.remove(2) >>> str [1, 3, 4, 5, 2, 6] 2.pop: 删除单个或多个元素,按位删除(根据索引删除) >>> str=[0,1,2,3,4,5,6] >>> str.pop(1) #pop删除时会返回被删除的元素

  • Golang切片删除指定元素的三种方法对比

    目录 前言 1.截取法(修改原切片) 2.拷贝法(不改原切片) 3.移位法(修改原切片) 3.1 方式一 3.2 方式二 4.性能对比 5.小结 前言 Go 并没有提供删除切片元素专用的语法或函数,需要使用切片本身的特性来删除元素. 删除切片指定元素一般有如下几种方法,本文以 []int 为例给出具体实现. 1.截取法(修改原切片) 这里利用对 slice 的截取删除指定元素.注意删除时,后面的元素会前移,所以下标 i 应该左移一位. // DeleteSlice1 删除指定元素. func D

  • C语言求阶乘之和的三种实现方法(先阶乘再累加)

    C语言求阶乘之和的三种实现方法(先阶乘再累加)

    目录 题目: 方法一:使用一层for循环实现 代码简单快捷容易理解 方法二:使用两层for循环嵌套 方法三:函数递归实现 总结 题目: 此处题目是以1-20的阶乘之和举例 方法一:使用一层for循环实现 代码简单快捷容易理解 代码示例如下: #include<stdio.h> int main() { double a = 1, sum = 0;//因为最后值可能会超出int所能接收的范围 故用double int n, i; scanf("%d", &n);//注

  • Go语言拼接URL路径的三种方法

    目录 JoinPath ResolveReference path.Join 参考 Go语言拼接URL路径有多种方法建议用ResolveReference. JoinPath JoinPath会把多个多个路径合并成一个路径,并且处理../和./,多个//合并成单个/. package main import (     "fmt"     "net/url" ) func main() {     u1 := "http://example.com/dir

  • MySQL不使用order by实现排名的三种思路总结

    假定业务: 查看在职员工的薪资的第二名的员工信息 创建数据库 drop database if exists emps; create database emps; use emps; create table employees( empId int primary key,-- 员工编号 gender char(1) NOT NULL, -- 员工性别 hire_date date NOT NULL -- 员工入职时间 ); create table salaries( empId int

  • R语言之左连接的三种实现操作

    数据处理中经常遇到表连接问题,本次介绍R语言中三种左连接方法,这三种是等价的,不过会有时间快慢问题,斟酌使用. 法一: > data0 <- merge(a,c,all.x=TRUE,by='CELLPHONE') 法二: > data1 <- sqldf('select a.*,b.* from a left join c on a.CELLPHONE=c.CELLPHONE') 法三: > data2 <- c[a,on='CELLPHONE'] 注意:第三种方法的

  • 关于python列表增加元素的三种操作方法

    1.insert方法,该方法包含两个参数,第一个参数为插入的位置参数,第二个参数为插入内容 a = [0,0,0] b = [1,2,3] a.insert(0,b) print a 输出: [[1, 2, 3], 0, 0, 0] 2.extend方法,该方法的参数为一个列表,将该指数所指定到的列表插入到原列表中 a = [0,0,0] b = [1,2,3] a.extend(b) print a 输出: [0, 0, 0, 1, 2, 3] 3.append方法,该方法后面只能带上一个参数

随机推荐