LeetCode： Remove Element

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.

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 a modification to the input array will be known to the caller as well.

Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.

Example 2:
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.

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

Solution #1

首先設定兩個計數器, 分別為 i 和 j counter。 使用 while 迴圈方式將 nums 集合內的每一個元素與預定要移除的值做比對。 如果『該元素的值』等於『移除的值』，則繼續跑ㄧ個元素。但是當該『元素的值』不等於『移除的值』的時候，則會讓該元素依序往前排列在集合內。 最後會回傳 i counter 代表著留下值的長度。

def remove_element(nums, val)
  i = 0
  j = 0
  while j < nums.length
    if nums[j] != val
      nums[i] = nums[j]
      i += 1
    end
    j += 1
  end
  return i
end

Explanation #1

# nums = [3,2,2,3]
# val = 3

#     第一圈：
#     i = 0
#     j = 0
#     while 0 < 4
#       if (nums[j]=>3) != 3 # won't enter the if logic
#       end
#       j = 1
#     end
#     nums = [3,2,2,3]

#     第二圈：
#     i = 0
#     j = 1
#     while 1 < 4
#       if (nums[j]=>2) != 3
#         nums[0] = 2
#         i = 1
#       end
#       j = 2
#     end
#     nums = [2,2,2,3]

#     第三圈：
#     i = 1
#     j = 2
#     while 2 < 4
#       if (nums[j]=>2) != 3
#         nums[1] = 2
#         i = 2
#       end
#       j = 3
#     end
#     nums = [2,2,2,3]

#     第四圈：
#     i = 2
#     j = 3
#     while 3 < 4
#       if 3 != 3       # won't enter the if logic
#       end
#       j = 4
#     end
#     nums = [2,2,2,3]

#     第五圈：
#     i = 2
#     j = 4
#     while 4 < 4
#     end
#     return 2
#     nums = [2,2,2,3]

Solution #2

這裡是運用了 Array 所提供的 compact! 方法來解題。基本上就是讓 each_with_index 方法跑每一個元素，只要是與移除的元素相同就會變成 nil。最後再以 compact! 移除掉 nil 就可以得到正確的集合元素跟規模大小了。

def remove_element(nums, val)
  return 0 if nums.length == 0
  nums.each_with_index do |num, index|
      if num == val
          nums[index] = nil
      end
  end
  nums.compact!
  nums.length
end