Remove Element

Question * Easy *

Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2

1
2
3
4
5
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

My solution

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int removeElement(int[] nums, int val) {
       boolean tt = true; 
       int k; 
       int f = 0;
       int temp;
      for(int z=0;z < nums.length;z++){
          if(nums[z] != val){
              f++;
          }          
      }
      for (int i=0; i<f;i++){
          tt = true;
          if (nums[i] == val ){
              k = i;
            while(tt){
               k++;
               if(nums[k] != val){
                   tt=false;
                   temp = nums[i];  
                   nums[i] = nums[k];
                   nums[k] = temp;
               }
                
            }
              
          }
      }          
 return f;       
        
    }
}

这个方法比较“笨”。 首先计算数组nums里面不等于val的个数 X。 最后就是利用循环，数组里面等于val的item被离这个item最近的不等于val的数字数字替代。 也可以说他们是交换位置。这是这个方法的思路。

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] != val){
                nums[index] = nums[i];
                ++index;
            }
        }
        
    return index;    
    }
}

这个方法说实话很巧，和Leetcode solution中的一个思路很像。 大致思路就是循环这个数组把不等于val 的item逐个移到数组的前面。返回的index也就是数组中不等于val的个数。

Leetcode Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

When we encounter nums[i]=val, we can swap the current element out with the last element and dispose the last one. This essentially reduces the array’s size by 1.

Note that the last element that was swapped in could be the value you want to remove itself. But don’t worry, in the next iteration we will still check this element.

Leetcode Clarification

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}