首页 > > 程序设计 > C/C++ >

删除排序数组中的重复数字

2018-06-17 23:13:24来源：未知阅读 ()

删除排序数组中的重复数字

描述：给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。

不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

样例

给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。

今天我在LinCode中做了这道题，下面是两种解法：

1、用时超时

class Solution {
public:
    /**
     * @param A: a list of integers
     * @return : return an integer
     */
    int removeDuplicates(vector<int> &nums) {
        // write your code here
         if(nums.size() == 0){ //时刻注意数组越界  
            return 0;  
        }  
        int a=0,b,sum=nums.size();
	    while(a!=sum-1)
	    {
	        if(nums[a]==nums[a+1])
		   {
			for(int j=0;j<sum-a;j++)
			nums[a+j]=nums[a+j+1];
			sum--;
	     	}
		    else if(nums[a]!=nums[a+1])
			a++;
	     }
	     return sum;
    }
};

for循环最好不要嵌套for循环，当输入数据过多时，运算次数几乎成几何倍增长

2、最后改法

class Solution {
public:
    /**
     * @param A: a list of integers
     * @return : return an integer
     */
    int removeDuplicates(vector<int> &nums) {
        // write your code here
         if(nums.size() == 0){ //时刻注意数组越界  
            return 0;  
        }  
        int a=0,b=1,sum=nums.size();
        for(int i=1;i<sum;i++)
        {
            if(nums[i]!=nums[a])
            {
                nums[++a]=nums[i];
                b++;
            }
        }
        nums.resize(b);
         return b;
    }
};