0

嘿，今天在课堂上问了一个技巧问题，我想知道是否有办法在数组中找到唯一数字，通常的方法是使用两个 for 循环并获取与其他所有不匹配的唯一数字我在 C++ 中为我的数组使用 std::vectors 并且想知道 find 是否可以发现唯一编号，因为我不知道唯一编号在数组中的位置。

4

6 回答 6

2

假设我们知道向量至少有三个元素（否则，这个问题没有意义），只需寻找与第一个不同的元素。如果恰好是第二个，当然，我们要检查第三个，看看是第一个还是第二个是唯一的，这意味着一些额外的代码，但大致：

std::vector<int>::const_iterator
findUniqueEntry( std::vector<int>::const_iterator begin,
                 std::vector<int>::const_iterator end )
{
    std::vector<int>::const_iterator result
        = std::find_if(
            next( begin ), end, []( int value) { return value != *begin );
    if ( result == next( begin ) && *result == *next( result ) ) {
        -- result;
    }
    return result;
}

（未经测试，但你明白了。）

于 2013-07-25T16:59:41.840 回答
1

正如其他人所说，排序是一种选择。然后，您的唯一值将在任一侧具有不同的值。

这是解决它的另一个选项，使用 std::find，在 O(n^2) 时间内（向量的一次迭代，但每次迭代迭代整个向量，减去一个元素。） - 不需要排序。

vector<int> findUniques(vector<int> values)
{
    vector<int> uniqueValues;

    vector<int>::iterator begin = values.begin();
    vector<int>::iterator end = values.end();
    vector<int>::iterator current;

    for(current = begin ; current != end ; current++)
    {
        int val = *current;
        bool foundBefore = false;
        bool foundAfter = false;
        if (std::find(begin, current, val) != current)
        {
            foundBefore = true;
        }
        else if (std::find(current + 1, end, val) != end)
        {
            foundAfter = true;
        }

        if(!foundBefore && !foundAfter)
            uniqueValues.push_back(val);
    }
    return uniqueValues;
}

基本上这里发生的事情是，我在当前元素之前的向量中的元素上运行 ::find，并且还在当前元素之后的元素上运行 ::find。由于我当前的元素已经具有存储在“val”中的值（即，它已经在向量中一次），如果我在当前值之前或之后找到它，那么它不是唯一值。

这应该找到向量中所有不唯一的值，无论有多少唯一值。

这是一些运行它并查看的测试代码：

void printUniques(vector<int> uniques)
{
    vector<int>::iterator it;
    for(it = uniques.begin() ; it < uniques.end() ; it++)
    {
            cout << "Unique value: " << *it << endl;
    }
}

void WaitForKey()
{
    system("pause");
}

int main()
{
    vector<int> values;
    for(int i = 0 ; i < 10 ; i++)
    {
            values.push_back(i);
    }
    /*for(int i = 2 ; i < 10 ; i++)
    {
            values.push_back(i);
    }*/
    printUniques(findUniques(values));
    WaitForKey();
    return -13;
}

作为额外的奖励：

这是一个使用映射的版本，不使用 std::find，并在 O(nlogn) 时间内完成工作 - n 用于 for 循环，log(n) 用于 map::find()，它使用红黑树。

map<int,bool> mapValues(vector<int> values)
{
    map<int, bool> uniques;
    for(unsigned int i = 0 ; i < values.size() ; i++)
    {
        uniques[values[i]] = (uniques.find(values[i]) == uniques.end());
    }
    return uniques;
}

void printUniques(map<int, bool> uniques)
{
    cout << endl;
    map<int, bool>::iterator it;
    for(it = uniques.begin() ; it != uniques.end() ; it++)
    {
        if(it->second)
            cout << "Unique value: " << it->first << endl;
    }
}

和一个解释。遍历vector<int>. 如果当前成员不在地图中，请将其值设置为true。如果它在地图中，请将值设置为false。之后，所有具有该值的值true都是唯一的，并且所有具有该值的值false都有一个或多个重复项。

于 2013-07-25T18:21:55.563 回答
0

如果您有两个以上的值（其中一个必须是唯一的），您可以通过第一次遍历数组并填充以该值作为键的映射，在时间和空间上在 O(n) 中完成，并评估键的出现次数。

然后，您只需遍历地图即可找到 1 的值。那将是一个唯一的数字。

于 2013-07-25T17:04:29.703 回答
0

你的意思是在一个只出现一次的向量中找到一个数字？如果是简单的解决方案，则嵌套循环。我不认为std::find或std::find_if在这里很有用。另一种选择是对向量进行排序，以便您只需要找到两个不同的连续数字。这似乎有点矫枉过正，但实际上它是 O(nlogn) 而不是 O(n^2) 作为嵌套循环：

void findUnique(const std::vector<int>& v, std::vector<int> &unique)
{
  if(v.size() <= 1) 
  {
    unique = v;
    return;
  }

  unique.clear();

  vector<int> w = v;
  std::sort(w.begin(), w.end()); 

  if(w[0] != w[1]) unique.push_back(w[0]);
  for(size_t i = 1; i < w.size(); ++i)
    if(w[i-1] != w[i]) unique.push_back(w[i]);

  // unique contains the numbers that are not repeated
}
于 2013-07-25T17:07:23.780 回答
0

假设给定一个数组size>=3，其中包含一个 value 实例A，而所有其他值都是B，那么您可以使用单个 for 循环来执行此操作。

int find_odd(int* array, int length) {
  // In the first three elements, we are guaranteed to have 2 common ones.
  int common=array[0];
  if (array[1]!=common && array[2]!=common) 
    // The second and third elements are the common one, and the one we thought was not.
    return common;

  // Now search for the oddball.
  for (int i=0; i<length; i++) 
    if (array[i]!=common) return array[i];
}

编辑：

K 如果 5 个数组中超过 2 个不同怎么办？- 极好的

啊……那是另一个问题。因此，您有一个 size 数组，其中包含不止一次n的公共元素，而所有其他元素仅包含一次。c目标是找到一组不常见的（即唯一的）元素，对吗？

那你需要看看上面Sylvain的回答。我认为他在回答一个不同的问题，但它会为此工作。最后，您将拥有一个包含每个值的计数的哈希映射。遍历hash map，每次看到值1，就知道key是输入数组中的唯一值。

于 2013-07-25T16:56:36.963 回答
0

此示例使用映射来计算出现次数。唯一编号只会出现一次：

#include <iostream>
#include <map>
#include <vector>

int main ()
{
  std::map<int,int> mymap;
  std::map<int,int>::iterator mit;

  std::vector<int> v;
  std::vector<int> myunique;

  v.push_back(10);  v.push_back(10);
  v.push_back(20);  v.push_back(30);
  v.push_back(40);  v.push_back(30);

  std::vector<int>::iterator vit;

  // count occurence of all numbers
  for(vit=v.begin();vit!=v.end();++vit)
  {
      int number = *vit;
      mit = mymap.find(number);
      if( mit == mymap.end() )
      {
          // there's no record in map for your number yet
          mymap[number]=1; // we have seen it for the first time
      } else {
          mit->second++; // thiw one will not be unique
      }
  }

  // find the unique ones
  for(mit=mymap.begin();mit!=mymap.end();++mit)
  {
      if( mit->second == 1 ) // this was seen only one time
      {
          myunique.push_back(mit->first);
      }
  }

  // print out unique numbers
  for(vit=myunique.begin();vit!=myunique.end();++vit)
      std::cout << *vit << std::endl;


  return 0;
}

此示例中的唯一数字是 20 和 40。对于此算法，不需要对列表进行排序。

于 2013-07-25T16:58:21.833 回答