reference binding to null pointer of type 'val

问题:

This is leetcode 26. Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. An example is given nums = [1,1,2], the function should return [1,2].

Below is my code. I delete all the other duplicates, just leave one of them. However I always got an error of "reference binding to null pointer of type 'value_type'" when submitting. I would appreciate if anyone can help me with this!

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        while(i < nums.size() - 1) {
            if (nums[i] == nums[i + 1]) {
                nums.erase(nums.begin() + i);
            } 
            else i++;
        }
        return nums.size();
    }
};

回答1:

vector<T>::size() returns a value of type size_t, which is an unsigned type. Let's say the vector passed in is empty and therefore the vector's length is 0. nums.size() - 1 will cause integer underflow and you will actually be comparing 0 with a very large positive number. This will evaluate to true causing the loop to run and i going pass the array bounds.

To fix this you can cast nums.size() to int preemptively or store the size in an integer variable and compare with that.

回答2:

The function, as posted, works fine for a vector whose elements are [1 1 2]. See https://ideone.com/ppuRg5.

However, one problem I see in your function is that if you pass it an empty vector, it's going to run into problems.

while(i < nums.size() - 1)

will be a problem when nums is empty. You can preemptively avoid that problem by returning from the function immediately if you find that it is an empty vector.

Also, use an unsigned type for i to avoid compiler warnings about comparing signed and unsigned types.

int removeDuplicates(std::vector<int>& nums) {
   if ( nums.empty() )
   {
      return 0;
   }

   unsigned int i = 0;
   while(i < nums.size() - 1) {
      if (nums[i] == nums[i + 1]) {
         nums.erase(nums.begin() + i);
      } 
      else i++;
   }
   return nums.size();
}

回答3:

This is not an answer to your question, but it would be more efficient solution to the problem if you didn't have to resize your vector each time you find a duplicate. Just to give you an idea, you could have two iterators i and j, i keeping the index of the last unique element of your solution vector and j iterating through the vector. When j points to a value not in the first i elements, copy that to v[i]. And once you are done, delete everything from the j-th place onwards.