LeetCode——oj练习之原地删除数值中的元素

我们来看这道题思路有如下:

1.利用循环判断数组的某个元素是否为需要移除的元素,如果是的话那么就将后面的元素先前覆盖一格,直到循环结束。

相关代码如下

时间复杂度为O(n^2)

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

}

2.创建一个新数组,遍历原数组,如果原数组的元素不是需要移除的那个,就把该元素放到那个新数组中,如果是需要移除的那个就跳过;

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

}

3.最优解法:让数组上下同时进行遍历,如果此时的元素不是要删除的元素,那么用自己去覆盖自己,否则向前跳;

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];
                src++;
                dest++;
            }

        }
        return dest;
}

这个思路无论是从时间复杂度还是空间复杂度来说都是最优解

经验分享 程序员 微信小程序 职场和发展