首页 > 代码库 > 【LeetCode】Remove Element

【LeetCode】Remove Element

2024-07-06 18:32:03   224人阅读

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn‘t matter what you leave beyond the new length.

 

解法一：使用vector记录每个elem的位置，介于这些位置之间的元素就可以前移相应的步长。比如，在vector[i]和vector[i+1]之间的元素可以前移i+1位。好处是没有多余的赋值移位操作，缺点是vector空间复杂度O(n)

class Solution 
{
public:
    int removeElement(int A[], int n, int elem) 
    {
        vector<int> tagv;
        int newlength = n;

        for(int i = 0; i < n; i ++)
            if(A[i] == elem)
                tagv.push_back(i);

        int sz = tagv.size();
        if(sz == 0)
            return newlength;
        else if(sz == 1)
        {
            for(int i = tagv[0]; i+1 < n; i ++)
                A[i] = A[i+1];
            return newlength-1;
        }
        else
        {
            for(vector<int>::size_type st = 0; st+1 < sz; st ++)
            {
                for(int i = tagv[st]+1; i < tagv[st+1]; i ++)
                    A[i-(st+1)] = A[i];//forward st+1
            }
            for(int i = tagv[sz-1]+1; i < n; i ++)
                A[i-sz] = A[i];
            return newlength-sz;
        }
    }
};

 

解法二：解法一的改进，使用count值记录目前是第几个elem，在遇到下一个elem之前，其间元素前移count位。

class Solution {
public:
    int removeElement(int A[], int n, int elem) 
    {
        int count = 0;

        for(int i = 0; i < n; i ++)
        {
            if(A[i] == elem)
            {
                count ++;
                while(i+1 < n && A[i+1] != elem)
                {
                    A[i+1-count] = A[i+1];
                    i ++;
                }
            }
        }
        return n-count;
    }
};

 

解法三：最naive的做法，设置一个新A数组的下标。遍历过程中遇到elem就跳过，否则就赋给新A数组下标对应元素。缺点是有多余的赋值。

class Solution {
public:
    int removeElement(int A[], int n, int elem) 
    {
        int newind = 0;
        for(int i = 0; i < n; i ++)
        {
            if(A[i] != elem)
                A[newind++] = A[i];
        }
        return newind;
    }
};

 

解法四：最优美的解法，当遍历过程中遇到elem，就用末尾的元素来填补。这样甚至遍历不到一次。

class Solution {
public:
    int removeElement(int A[], int n, int elem) 
    {
        int newlength = n;
        for(int i = 0; i < newlength; i ++)
        {
            if(A[i] == elem)
            {
                A[i] = A[newlength-1];
                i--;
                newlength--;
            }
        }
        return newlength;
    }
};


联系
我们