C++ 哪个数字不属于？

Question

我是编程的初学者，但在编写自己的程序时，我遇到了似乎无法绕过的障碍。

无论如何，给定数组中的一组数字:

4
14
24
27
34

您可以看到除了一个数字之外，所有数字的个位都是 4。我将如何编写一个函数来返回不同位置的数字，在本例中为 27？每次程序运行时数字都会不同，但由于场景的原因，其中 4 个总是在个位上有相同的数字。它们不一定按数字顺序排列。

我似乎无法找到一种数学方法，也无法通过搜索找到任何东西。有什么想法吗？

Answer 1

Jerry Coffin 的解决方案是不必要的 O(log N)；它可以通过使用 std::partition 而不是 std::sort 来改进:

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

int main() {
    std::vector<int> n = {4, 14, 27, 24, 34};

    int first = n[0]%10;    
    std::partition(std::next(std::begin(n)), std::end(n),
                   [&](int a) { return first == a%10;});

    std::cout << ((first != n[1]%10) ? n.front() : n.back());
}

但这仍然做了太多的比较。该问题最多可以通过 (N+1)/2 比较来解决:

#include <iostream>
#include <vector>

int odd_man_out(const std::vector<int> n) {
    size_t i;
    for (i = 0; i + 2 < n.size(); i += 2) {
      if (n[i]%10 != n[i+1]%10)
        return n[i]%10 != n[i+2]%10 ? i : i + 1;
    }
    if (i + 2 == n.size() && n[i]%10 == n[i-1]%10)
      return i + 1;
    else
      return i;
}

int main() {
    std::vector<int> n = {4, 14, 27, 24, 34};
    std::cout << n[odd_man_out(n)];
}