首页 > itarticle > 27. remove element

27. remove element

admin 11月 13, 2020 0

Question

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.

Analysis

三种情况

  1. 如果nums[end] == val，end–，直到nums[end] != val
  2. 如果nums[start] == val, 交换nums[start] and nums[end], start++; end–
  3. nums[start] != val, start++, 继续循环

Java only pass by value. Java does not pass by reference

Complexity

Worst Case:

All numbers are target num. Time Complexity is O(n)

It is In-Place use O(1) to swap

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
public int (int[] nums, int val) {·
        if (nums == null || nums.length == 0) return 0;
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (nums[end] == val) {
                end--;
            } else if (nums[start] == val) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                end--;
            } else {
                start++;
            }
        }
        
        return end + 1;
    }
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能