1

给定一个整数向量，遍历该向量并检查是否有多个相同的数字。在这种情况下，请删除它们，以便只有向量的单个索引包含该数字。这里有一些例子：

vector<int> arr {1,1,1,1}
When arr is printed out the result should be 1.

vector<int> arr {1,2,1,2}
When arr is printed out the result should be 1,2.

vector<int> arr {1,3,2}
When arr is printed out the result should be 1,3,2.

我知道对此有很多解决方案，但我想用我的方法解决它。我看过的解决方案使用了很多内置函数，作为初学者，我不想太适应。我想锻炼我解决问题的能力。

这是我的代码：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> arr {1,1,1,1,2,1,1,1,1,1};

    for (int i {}; i < arr.size(); ++i)
    {
        int counter {};
        
        for (int j {}; j < arr.size(); ++j)
        {
            if (arr.at(i) == arr.at(j))
            {
                counter++;
                
                if (counter > 1)
                    arr.erase(arr.begin()+j);
            }
        }
    }
    
    //Prints out the vector arr
    
    for (auto value : arr)
    {
        cout << value << endl;
    }

    return 0;
}

问题是它在大多数情况下都有效，除了一些让我感到困惑的情况。

例如：

vector<int> arr {1,1,1,1,2,1,1,1,1,1}
When arr is printed out the result is 1,2,1 instead of 1,2.

但是，在这种情况下：

vector<int> arr {1,1,1,1,2,1,1,1}
When arr is printed out the result is 1,2.

它似乎在绝大多数情况下都有效，但是当一个数字在向量中重复很多次时，它似乎不起作用，我似乎找不到原因。

我现在要求您首先告诉我问题的原因，然后指导我应该如何使用我的解决方案来解决这个问题。

4

3 回答 3

1

我使用的机器有一个预 C++11 编译器，所以这是老式 C++ 的答案。解决这个问题的简单方法是向后擦除。这样你就不用担心大小了。此外，不要使用可以优化的 for 循环，而是使用 while 循环。

#include <iostream>
#include <vector>

int main()
{
    int dummy[] = {1,1,1,1,2,1,1,1,1,1};
    std::vector<int> arr(dummy, dummy + sizeof(dummy)/sizeof(dummy[0]));

    size_t ii = 0;
    while (ii < arr.size())
    {
        // Save the value for a little efficiency
        int value = arr[ii];

        // Go through backwards only as far as ii.
        for (size_t jj = arr.size() - 1; jj > ii; --jj)
        {
            if (value == arr[jj])
                arr.erase(arr.begin() + jj);
        }
        ++ii;
    }
    
    
//Prints out the vector arr
    
    for (size_t ii = 0; ii < arr.size(); ++ii)
    {
        std::cout << arr[ii] << std::endl;
    }

    return 0;
}
于 2022-02-08T23:12:12.910 回答
0

这个内部 for 循环不正确

    int counter {};
    
    for (int j {}; j < arr.size(); ++j)
    {
        if (arr.at(i) == arr.at(j))
        {
            counter++;
            
            if (counter > 1)
                arr.erase(arr.begin()+j);
        }
    }

如果删除了元素，则j不应增加索引。否则，删除后的下一个元素将被绕过，因为向量中已删除元素之后的所有元素都向左移动了一个位置。

使用变量counter是多余的。只需使用j = i + 1.

使用您的方法，程序可以如下所示

#include <iostream>
#include <vector>

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

    for ( decltype( arr )::size_type i = 0; i < arr.size(); ++i)
    {
        for ( decltype( arr )::size_type j = i + 1; j < arr.size(); )
        {
            if (arr.at( i ) == arr.at( j ))
            {
                arr.erase( arr.begin() + j );
            }
            else
            {
                j++;
            }
        }
    }


    //Prints out the vector arr

    for (auto value : arr)
    {
        std::cout << value << std::endl;
    }
}

程序输出为

1
2

当每个重复的元素被单独删除时，这种方法效率低下。最好使用所谓的擦除删除习语。

这是一个演示程序。

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

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

    for (auto first = std::begin( arr ); first != std::end( arr ); ++first)
    {
        arr.erase( std::remove( std::next( first ), std::end( arr ), *first ), std::end( arr ) );
    }

    //Prints out the vector arr

    for (auto value : arr)
    {
        std::cout << value << std::endl;
    }

}
于 2022-02-08T22:50:43.703 回答
0

如评论中所述，当您erase找到重复项（在 index 处j）时，您可能会修改元素在 index 处的位置i。

因此，在您调用 之后arr.erase(arr.begin() + j)，您需要i相应地进行调整，如果它指的是在删除元素之后出现的元素。

这是您的功能的“快速修复”：

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> arr{ 1,1,1,1,2,1,1,1,1,1 };
    for (size_t i{}; i < arr.size(); ++i) {
        int counter{};
        for (size_t j{}; j < arr.size(); ++j) {
            if (arr.at(i) == arr.at(j)) {
                counter++;
                if (counter > 1) {
                    arr.erase(arr.begin() + j);
                    if (i >= j) --i; // Adjust "i" if it's after the erased element.
                }
            }
        }
    }

    //Prints out the vector arr
    for (auto value : arr) {
        std::cout << value << std::endl;
    }
    return 0;
}

正如评论中还提到的，还有其他方法可以使功能更高效；但是，您已表示要“练习自己的解决问题的能力”（这是非常值得称赞的），因此我将坚持为您的紧迫问题提供解决方案。

于 2022-02-08T22:34:32.590 回答