从数组C++中删除重复项

问题描述 投票：0回答：9

我正在尝试创建一个调用 2 个函数的简单程序。
第一个函数采用部分填充的数组，循环遍历它并删除所有重复的值。当从数组中删除一个值时，剩余的数字将向后移动以填补空白，即当函数完成时，数组的所有空值将在末尾在一起。

第二个函数打印更新后的数组。

我当前的代码如下。目前，当我运行代码时，控制台显示：

2 6 0 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460 -858993460
。
它应该显示：
1 2 5 6

另外，我不知道如何向后移动数组的剩余元素，以便空值在最后会在一起。

#include <iostream>

using namespace std;

void deleteRepeats(int *arr, int arraySize, int& posUsed);
void printArray(int *arr, int arraySize);

int main()
{
    int arr[10] = { 1, 2, 2, 5, 6, 1};
    int posUsed = 6;
    int arraySize = 10;


    deleteRepeats(arr, arraySize, posUsed);
    printArray(arr, arraySize);

    return 0;
}

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
    for (int i = 0; i < arraySize; i++)
    {
        for (int j = i; j < arraySize; j++)
        {
            if (arr[i] == arr[j])
            {
                for (int k = j; k < arraySize; k++)
                {
                    arr[k] = arr[k + 1];

                }
                posUsed--;
            
            }
            else
                j++;
        }
    }
}

void printArray(int *arr, int arraySize)
{
    for (int i = 0; i < arraySize; i++)
    {
        cout << arr[i] << "  ";
    }
}
c++ arrays duplicates
9个回答
3
投票

我会让标准容器做你喜欢做的事情。

  • 对向量进行排序
  • 使用 
    erase
    和 
    unique
    删除重复项。

这是代码

#include <vector>
#include <iostream>
#include <algorithm>

void print(const std::vector<int> &arr){
    for (const auto & i : arr){
        std::cout << i <<" ";
    }
    std::cout <<"\n";
}

int main() {
    std::vector<int> arr{1, 2, 2, 5, 6, 1};    
    print(arr);

    std::sort( arr.begin(), arr.end() );
    arr.erase( std::unique( arr.begin(), arr.end() ), arr.end() );

    print(arr);
}

诗。使用 

int *arr, int arraySize
不太像 C++。请始终尝试使用合适的容器（几乎总是
std::vector
）。

编辑： 我稍微改变了我的答案，因为我发现了这个速度比较（实际上整个问题都得到了回答）。 删除重复项并对向量进行排序的最有效方法是什么？

2
投票

考虑到你的赋值约束（更像 C，而不是惯用的 C++），你可以像这样重写你的函数，以使其工作：

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
    for (int i = 0; i < posUsed; ++i)
    {
        int duplicates = 0;
        int j = i + 1;
        // find the first duplicate, if exists
        for ( ; j < posUsed; ++j)
        {
            if ( arr[i] == arr[j] ) {
                ++duplicates;
                break;
            }
        }
        // overwrite the duplicated values moving the rest of the elements...
        for (int k = j + 1; k < posUsed; ++k)
        {
            if (arr[i] != arr[k])
            {
                arr[j] = arr[k];
                ++j;
            }
            // ...but skip other duplicates
            else
            {
                ++duplicates;    
            }
        }
        posUsed -= duplicates;
    }
    // clean up (could be limited to the duplicates only)
    for (int i = posUsed; i < arraySize; ++i)
        arr[i] = 0;
}
2
投票

可能更容易想象该算法具有单独的输入和输出数组。然后，用伪代码：

for i = 0 to input_array_size-1
    Is input[i] equal to input[j] for any j between 0 and i-1?
    Yes - do nothing
    No - copy input[i] to output

要通过共享输入和输出来实现此目的，您需要有两个数组大小：

input_array_size
和
output_array_size
。那么，伪代码就变成了

output_array_size = 0
for i = 0 to input_array_size-1
    Is array[i] equal to array[j] for any j between 0 and output_array_size-1?
    Yes - do nothing
    No:
        copy array[i] to array[output_array_size]
        Increase output_array_size

注意：它将输出写入曾经输入的位置，因此检查重复项应该查看输出的所有元素。例如，如果您的数组是 

1, 2, 1, 3, 5, 6, 3
，那么对于最后一个 
3
，累积输出是 
1, 2, 3, 5, 6
，并且代码应将所有这些与当前元素进行比较。

为了简化调试，当它说“不执行任何操作”时，您可以将当前元素设置为-1。这样，如果您在执行期间打印数组（用于调试），将更清楚哪些元素被删除。

1
投票

如您所见，仅进行了两处更改

1：您正在遍历整个数组，因为您声明了一个 

posUsed=6
变量，这是因为只有 6 个元素，因此在循环中，您需要在数组中遍历到 
posUsed
索引，如 
i<posUsed
j<posUsed
k<posUsed

2：第二个更改是在 j 循环中 

j=i+1
因为您不需要将任何索引的元素与相同索引的元素进行比较，您必须将其与该索引之后的元素进行比较。如果您将它与相同的元素进行比较，它将是相同的，并且程序将删除该相同的元素，从而导致错误。

更重要的是，我们不会在 

posUsed
索引之后进行遍历，因为之后数组已经为空/零或 null，无论你怎么称呼它

如果您只想显示非重复元素而不是数组末尾的零，只需在 

if(arr[i]==0) return;
函数循环中的 
printArray
语句之前添加 
cout

void deleteRepeats(int *arr, int arraySize, int& posUsed)
{
{
    for (int i = 0; i < posUsed; i++)
    {
        for (int j = i+1; j < posUsed; j++)
        {
            if (arr[i] == arr[j])
            {
                for (int k = j; k < posUsed; k++)
                {
                    arr[k] = arr[k + 1];
                    
                }
            }
        
        }
    }
}
}
0
投票

使用两个指针
如果数组已排序

    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int i = 0;

        for(int j = 1; j < nums.size(); j++)
            if(nums[j] != nums[i])  nums[++i] = nums[j];

        // return new array length
        return i + 1;
    }

//input: [1, 1, 2, 1] (arr1)
//output: 2 (returned length)
// print unique element
for(int i = 0; i < output; i++) cout << arr1[i] << '\n';
// [1, 2]

time complexity: O(N/2) -> O(N)
space complexity: O(1)
0
投票

从未排序的数组中删除重复元素的复杂度为 O(n^2)。

    for (i = 1; i < vec.size(); i++)
    {
        for (j = 0; j < i; j++)
        {
            if (vec[i] == vec[j])
            {
                vec[i] = -1; //Every duplicate element will replace by -1
            }
        }
    }

   for (i = 0; i < vec.size(); i++)
    {
        if (vec[i] != -1)
        {
            copy.push_back(vec[i]);

     /*if you are using an array then store this value into a new array.
       first, declare a new array. The new array size will be equal to the 
       previous array. Like this :
       int newArr[sizeOfPreviousArrary];
       int j = 0;
       newArr[j] = arr[i]; 
       j++;
     */

        }
    }
0
投票

使用地图或集合删除重复项

void removeDuplicates(int arr[], int n)
{
  
    int i;
  
    // Initialise a set
    // to store the array values
    set<int> s;
  
    // Insert the array elements
    // into the set
    for (i = 0; i < n; i++) {
  
        // insert into set
        s.insert(arr[i]);
    }
  
    set<int>::iterator it;
  
    // Print the array with duplicates removed
    cout << "\nAfter removing duplicates:\n";
    for (it = s.begin(); it != s.end(); ++it)
        cout << *it << ", ";
    cout << '\n';
}
0
投票
#include <iostream>

using namespace std;

void removedup(int *arr, int &s)
{
    for (int i =0; i<s-1; i++)
    {
        for (int j=i+1; j<s; j++)
        {
            if (arr[i]==arr[j])
            {
                for (int k=j; k<s-1; k++)
                {
                    arr[k] = arr[k+1];
                }
                s--;
                j--;
            }
        }
    }
    for (int i=0; i<s; i++)
    {
        cout << arr [i] <<" ";
    }
    cout << endl ;
}

int main() {
    int n;
    cout << "enter the size of array" << endl;
    cin >> n;
    int *arr = new int[n];
    for (int i=0; i<n; i++)
    {
        cin >> arr [i];
    }
    for (int i=0; i<n; i++)
    {
        cout << arr[i] <<" ";
    }
    cout << endl;
    removedup(arr,n);
    return 0;
}
0
投票

以 O(n) 复杂度从排序数组中删除重复元素。

for (i = 0; i < n; i++)
{
    if (arr[i] != arr[i+1]){
            vec.push_back(arr[i]);
        
        /*if you are using an array then store this value into a new array.
        first, declare a new array. The new array size will be equal to the 
        previous array. Note the array must be declared outside of the loop or it will be destroyed. 
        Like this :
            int newArr[sizeOfPreviousArrary];
            int j = 0;
            newArr[j] = arr[i]; 
            j++;
        */
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.