Interview question 17.04 in leetcode Disappearing numbers and 27 Removing Elements

17.04. Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer . You have a way O(n) Is it finished in time ？

Example 1：

Input ：[3,0,1]
Output ：2
 

Example 2：

Input ：[9,6,4,2,3,5,7,0,1]
Output ：8

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/missing-number-lcci

  The time complexity required in the question shall not exceed O（n）, Then the realizable method can be ： Find out first 0 To n The sum of all integers , Then subtract the array nums The elements in , What you get is the missing integer . The input is the array and the number of array elements .

int missingNumber(int* nums, int numsSize){
    int x=numsSize*(numsSize+1)/2;
    for(int i=0;i<numsSize;i++)
    {
        x=x-nums[i];
    }
     return x;
}

27. Remove elements

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

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 .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/remove-element

  The question requires modification in place , The space complexity is O（1）, Then you can use the double pointer method , Traversal array , If it is equal to val Value , So skip , If it's not equal, stay . Return is not equal to val Number of elements of value .

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