[delete specified number leetcode]

partners , Hello, everyone , Today I share with you for the first time in leetcode Brush the first question , If there is anything inappropriate, you are welcome to correct this rookie's mistakes .

 

 

  Before the formal question brushing , We also need to know something OJ Simple classification of questions ：

1. IO type
2. Interface type

In short IO Type is to pass scanf Enter some data , adopt printf Output some data . The interface type does not need its own input and output , You only need to implement specific functions （ You don't need to cite things like header files ）, and leetcode Most of the above topics are interface type , It's very comfortable to brush , Today I experienced a , It's really comfortable .

 

The digression is over , Next, let's start our topic ：

1 Delete the specified number

Portal

Give you an array nums  And a value val, You need In situ Remove all values equal to  val  The elements of , And return the new length of the array after removal . Don't use extra array space , You have to use only O(1) Additional space and In situ Modify input array . The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

 

explain :

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on 「 quote 」 By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments
int len = removeElement(nums, val);

// Modifying the input array in a function is visible to the caller .
// Based on the length returned by your function , It prints out the array Within this length All elements of .
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 

 

Example 1：

Input ：nums = [3,2,2,3], val = 3
Output ：2, nums = [2,2]

explain ： Function should return the new length 2, also nums The first two elements in are 2. You don't need to think about the elements in the array that follow the new length . for example , The new length returned by the function is 2 , and nums = [2,2,3,3] or nums = [2,2,0,0], It will also be seen as the right answer .

Example 2：

Input ：nums = [0,1,2,2,3,0,4,2], val = 2
Output ：5, nums = [0,1,4,0,3]

explain ： Function should return the new length 5, also nums The first five elements in are 0, 1, 3, 0, 4. Note that these five elements can be in any order . You don't need to think about the elements in the array that follow the new length .
 

Tips ：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

---

 

2 Solution 1

Traverse every element in the array , Judge whether the element is a deleted number , If it is , Just move all the elements behind the number forward by one digit , Until all arrays are traversed .

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

        numsSize--;
        i--;
    }
}

return numsSize;
}

This method is the easiest to think of , It's easy to implement , If implemented in this way , The time complexity is O(N^2), The space complexity is O(1), Not a particularly good method .

leetcode The execution time and memory consumption on are related to the network speed , You don't have to pay attention to this .

 

---

3 Solution 2

If we recreate an array , Traversing the target array will not delete the values of the elements and assign them to our newly created array one by one .

But this method certainly does not meet the requirements of this topic , Here is just an idea .

  Specific code ：

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

If implemented in this way , The time complexity is O(N), But the spatial complexity is also O(N), This feels like trading space for time , This method is obviously not a good one , Is there a better way ？

---

4 Problem solving idea 3

Through the second way of thinking, we know that we have opened up additional space to assign the elements that are not deleted one by one , So can you assign elements to the past without opening up additional space ？ The answer, of course, is yes . You can define two variables src and dest, Then iterate through the array , Compare the array with the deleted element , If not , First subscript src The value of the element of is assigned to the subscript dest Elements , let src and dest , respectively, ++, If you delete an element , Let's just src++, Give Way src Find the value in the array that is not equal to the deleted element , Put it in dest Point to the position .

Specific code implementation ：

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;
}

If implemented in this way , The time complexity is O(N), The space complexity is O(1), This method is obviously better than the previous two methods .

  Okay , Today's sharing is here