从排序数组中删除重复项
给定一个排序数组，删除重复项，使每个元素仅出现一次并返回新长度。
请注意，即使我们希望您返回新长度，也请确保就地更改原始数组
不要为另一个数组分配额外的空间，必须使用常量内存来执行此操作。
我尝试了以下代码，任何人都可以帮助我哪里出了问题吗？
#include<iostream>
#include<vector>
using namespace std;
int removeDuplicates(vector<int> &A) {
int m=A.size();
if(m<=1) return m;
vector<int> :: iterator i=A.begin();
vector<int> :: iterator j=A.begin()+1;
vector<int> :: iterator temp;
while(i!=A.end() && j!=A.end())
{
while(j!=A.end() && *i == *j)
{
temp=j;
j++;
A.erase(temp);
}
i=j;
j++;
}
return A.size();
}
int main()
{
vector<int> vec={0,0,0,0,0,0,0,4,4,7,7,7,7,9};
cout<<"ans="<<removeDuplicates(vec);
return 0;
}
当您递增
jerase更好的方法是简单地将非重复元素从一个迭代器复制到另一个迭代器，并在主循环末尾设置新的长度。您当前的方法可能是 O(n^2)，对于实际使用来说太慢了。
我想这就是你所需要的。该函数从尾部到头部循环数组并计算相同的值。然后对唯一的值执行已经唯一的值的移位。 它不会改变向量的实际大小，因为它可能涉及向量内部内存的重新分配。
int removeDuplicates(vector<int> &vec) {
int currentVal = vec.size() - 1;
int uniqueNumber = 0;
while (currentVal >= 0) {
++uniqueNumber;
int sameVal = currentVal;
while (sameVal > 0 && vec[sameVal - 1] == vec[currentVal])
--sameVal;
int shiftSize = uniqueNumber;
for (int k = 1; k < shiftSize; ++k) {
vec[sameVal + k] = vec[currentVal + k];
}
currentVal = sameVal - 1;
}
return uniqueNumber;
}
系统会要求您使用数组。尽管向量在很多方面都很相似，但它并不相同。看看下面的示例代码。
此外，您还需要保持分配的内存相同。您无法确保使用向量，一旦添加/删除元素，它的大小就会增长/缩小，并且当删除元素时，向量后面的数组中的数据将被重新分配和重写。
int main()
{
int arr[14] = {0,0,0,0,0,4,4,4,4,5,5,5,7,9};
int last_non_duplicate_index = 0;
int current_index = 0;
int size = 14;
int new_size = size;
bool is_last_value = false;
// you can use for interchangeably
while(!is_last_value)
{
current_index++; // move one position ahead
if(current_index < size) // out of bonds check
{
if(arr[last_non_duplicate_index] != arr[current_index]) // value at position of current index is different
{
last_non_duplicate_index++; // increase index of the last value which was not a duplicate by one
arr[last_non_duplicate_index] = arr[current_index]; // write at that index
// e.g. if last index was 0 -> increase it to 1 and rewrite whatsever under arr[1] (current index)
}
else // values are the same
{
new_size--; // devrease the size
}
}
else
{
is_last_value = true; // current_index >= size -> out of bonds
}
}
for (int i = 0; i < new_size; i++)
{
std::cout << "arr[" << i << "]" << " = " << arr[i] << std::endl;
}
std::cout << "New size: " << new_size << std::endl;
return 0;
}
你可以使用这样的迭代器来做到这一点：
#include<iostream>
#include<vector>
using namespace std;
int removeDuplicates(vector<int> &A) {
int m = A.size();
if(m <= 1) return m;
for (auto it1 = A.begin(); it1 != A.end(); it1++) {
for (auto it2 = it1 + 1; it2 != A.end();) {
if (*it1 == *it2) {
it2 = A.erase(it2);
} else {
it2++;
}
}
}
return A.size();
}
int main()
{
vector<int> vec = { 0, 0, 0, 0, 0, 0, 0, 4, 4, 7, 7, 7, 7, 9 };
cout << "ans=" << removeDuplicates(vec);
return 0;
}
#TC : O(n)
#SC : O(1)
def removeDuplicates(arr,n):
# If array has no elements or only one element, return n
if (n==0 and n==1):
return n
# arr = [1,2,2,3,4,4,4,5,5]
# When i = 0, j= 0 arr=[1,2,2,3,4,4,4,5,5], arr[0] != arr[1], hence arr[0] = arr[0] and j =1, Increment i
# When i = 1, j = 1 arr[j] =[1,2,2,3,4,4,4,5,5]. arr[1] == arr[2], hence increment i
# When i = 2, j = 1 arr[j] = [1,2,2,3,4,4,4,5,5] arr[2] != arr[3], hence arr[1] = arr[2] j = 2, increment i
# When i =3, j = 2 arr[j] = [1,2,3,3,4,4,4,5,5] arr[3] != arr[4], hence arr[2] = arr[3] and j = 3, Increment i
# When i = 4, j = 3 arr[j] =[1,2,3,3,4,4,4,5,5] arr[4] == arr[5], hence increment i
# When i = 5, j = 3 arr[j] = [1,2,3,3,4,4,4,5,5] arr[5] == arr[6], hence increment i
# When i = 6, j = 3 arr[j] = [1,2,3,4,4,4,4,5,5] arr[6] != arr[7], hence arr[3] = arr[6] and j = 4, Increment i
# When i = 7, j= 4 arr[j] = [1,2,3,4,4,4,5,5] arr[7] == arr[8], hence Increment i
# End of for loop
j = 0
for i in range(0,n-1):
if arr[i] != arr[i+1]:
arr[j] = arr[i]
j = j + 1
# Check for the last index element and copy it to a[j]. Increment the j and return j
# When j = 4 arr[j] = [1,2,3,4,5,4,4,5,5] increment j
# j = 5
arr[j] = arr[n-1]
j = j + 1
return j
if __name__=="__main__":
arr = [1,2,2,3,4,4,4,5,5]
#arr = [1,1,2]
#arr = [2,2,2,2,2]
n = len(arr)
print(removeDuplicates(arr,n))
https://leetcode.com/problems/remove-duplicates-from-sorted-array/ [Leetcode问题链接][1]
class Solution:
def removeDuplicates(self, arr: List[int]) -> int:
n=len(arr)
i=0
for j in range(1,n):
if arr[i]!=arr[j]:
arr[i+1]=arr[j]
i+=1
return i+1