3

这是一个大数据，包含一亿个整数，但其中与其他相同的整数有一个不同的值，例如：1,1,1,1,1,1,1,42,1,1,1, 1..但是，我不知道我的以下代码发生了什么。

int main() {

    vector <int> data;
    cout << "Enter same numbers " << " and a different one( negative to be end) :" << endl;
    int value;
    while (cin >> value && value > 0) {
        data.push_back(value);
    }
    int unique_value;
    int size = data.size();
    if (data[0] != data[size - 1]) {
        if (data[0] != data[2]) {
            unique_value = data[0];
        } else {
            unique_value = data[size - 1];
        }
        cout << "found the unique number: " << unique_value << endl;
        exit(0);
    }
    int low = 1;
    int high = size - 2;
    while (high > low) {
        if (data[high] != data[low]) {
            //其中必有一个是不同的，只要和data[0]就能得到结果
            if (data[high] != data[0]) {
                unique_value = data[high];
            } else {
                unique_value = data[low];
            }
            break;
        }
    }
    if (high == low) {
        unique_value = data[high];
    }
    cout << "found the unique number: " << unique_value << endl;
    return 0;
}
4

4 回答 4

9

对前三个元素进行排序，然后取中间一个。这是您的非唯一号码。浏览列表，并查找与它不同的数字：

int data[] = {7,7,7,7,7,7,42,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7};
size_t N = sizeof(data)/sizeof(data[0]);
sort(data, data+3);
int non_unique = data[1];
for (int i = 0 ; i != N ; i++) {
    if (data[i] != non_unique) {
        cout << data[i] << endl;
        break;
    }
}

链接到ideone。

于 2012-09-07T01:23:29.747 回答
0

假设您只允许输入两个可能的数字（“一个不同的值与其他整数”），您不需要全部存储它们。在这种情况下，您将输入类似1,1,1,1,1,1,1,42,1,1,1,1.

如果是这种情况，您可以使用类似（伪代码）：

firstNum = 0; firstCount = 0
secondNum = 0; secondCount = 0
while true:
    num = getNumber()
    if num < 0:
        break while

    if firstCount == 0:                  # first unique number
        firstNum = num
        firstCount = 1
        next while

    if num == firstNum:                  # copy of first
        firstCount++
        next while

    if secondCount == 0:                 # second unique number
        secondNum = num
        secondCount = 1
        next while

    if num <> secondNum:                 # third unique number (disallowed)
        print "Only two numbers allowed"
        stop run

    secondNum++                          # was the second unique number

if secondNum == 0:                       # there was < 2 unique numbers
    print "Not enough different numbers"
    stop run

if firstCount > 1 and secondCount > 1:   # there were no unique numbers
    print "No one unique number"
    stop run

if firstCount == 1:                      # Choose number with count of 1
    print "Unique number is " firstNum
else
    print "Unique number is " secondNum

相反，如果可能有许多不同的数字，您将需要一个解决方案来检查每个数字与其他数字。

这可以通过多种方式完成（可能还有其他方式，这些只是最初想到的几个）：

  • 慢 O(n^2) 检查每个数字与每个其他（后续）数字。
  • 然后排序稍微快一些（可能是 O(log N)，然后通过排序列表检查相邻的数字。
  • 如果输入范围有限，您可以为每个可能的数字使用一个计数数组，并查找最终计数为 1 的那个（确保没有其他人也这样做）。

根据您的问题文本，我认为情况并非如此，但我认为我最好也涵盖这方面。

于 2012-09-07T01:27:13.397 回答
0

每个人都告诉过你他们会怎么做，但没有回答你的问题：你的代码有什么问题？

问题是您的代码永远不会终止，因为您永远不会更改循环中的highandlow值。您正在从数组的两端工作，并将两个值与数组中的第一个元素进行比较。现在，这使您的第一个 if 块变得多余，实际上有点奇怪，因为它检查第三个数组元素（没有任何边界检查）。

所以......把这部分拿出来：

//if (data[0] != data[size - 1]) {
//    if (data[0] != data[2]) {
//        unique_value = data[0];
//    } else {
//        unique_value = data[size - 1];
//    }
//    cout << "found the unique number: " << unique_value << endl;
//    exit(0);
//}

并修复循环：

int low = 1;
int high = size - 1;
while (high >= low) {
    if( data[high] != data[0] )
    {
        if (data[low] == data[high]) {
            unique_value = data[high];
        } else {
            unique_value = data[0];
        }
        break;
    }
    else if( data[low] != data[0] )
    {
        unique_value = data[low];
        break;
    }
    low++;
    high--;
}

// Take out the part that compares high==low.  It was wrong, and has been made
// redundant by looping while high >= low (instead of high > low).

那应该行得通。但这很奇怪。

现在，请注意，由于缓存局部性，以这种方式搜索您的数组是一个坏主意。出于优化原因，您希望将搜索限制在内存的同一部分，并且对于此算法，您没有理由不只检查数组中的三个相邻值。

事实上，您只需要检查前三个，之后您将确定非唯一值，或两者兼而有之。如果前三个元素都相同，则只需对数组的其余部分进行线性搜索，直到找到不同的值……已经指出，您甚至不必将值读入数组. 您可以即时执行此操作。

size_t size = data.size();

if( size < 3 ) {
    cerr << "Not enough data\n";
    exit(0);
}

int unique_val = 0;

if( data[1] == data[0] && data[2] == data[0] ) {
    int common_val = data[0];
    for( int i = 3; i < size; i ++ ) {
        if( data[i] == common_val ) continue;
        unique_val = data[i];
        break;
    } 
}
else if( data[1] != data[0] ) {
    if( data[2] == data[1] )
       unique_val = data[0];
    else
       unique_val = data[1];
}
else {
    unique_val = data[2];
}

if( unique_val == 0 ) {
    cout << "No unique value found\n";
} else {
    cout << "Unique value is " << unique_val << "\n";
}
于 2012-09-07T02:39:18.513 回答
0

首先是您的代码有什么问题。您有一个while由两个变量控制的循环，high并且low在循环内没有更新，因此它将永远旋转。

至于算法，您不需要存储数字来找到不同的数字，而是可以读取前两个数字，如果它们不同，则读取第三个数字并且您有答案。如果它们相同，请保留其中一个并继续阅读数字，直到找到一个不同的数字：

// omitting checks for i/o errors, empty list and single number list:
// and assuming that there is one that is different
int main() {
   int first;
   int current;
   std::cin >> first >> current; 
   if (first != current) {
      int third;
      std::cin >> third;
      if (first==third) {
         std::cout << current << "\n";
      } else {
         std::cout << first << "\n";
      }
      return 0;
   }
   while (std::cin >> current && current == first) ;
   std::cout << current << "\n";
}

在该草图之上，您将需要处理输入错误，以及不受该通用算法管理的极端情况（空列表、1 个元素列表、2 个元素列表）。

于 2012-09-07T02:32:19.097 回答