0

私はプログラミングの初心者のようなものですが、自分でプログラムを書いているときに、回避できないような障害に遭遇しました。

とにかく、配列内のこれらのような数字のセットが与えられた場合：

4
14
24
27
34

1つを除くすべての数字が1の場所に4を持っていることがわかります。1の場所で異なる数（この場合は27）を返すことができる関数をどのように作成しますか？プログラムを実行するたびに数字は異なりますが、シナリオにより、そのうちの4つは常に1の位で同じ数字になります。それらは必ずしも番号順になるとは限りません。

数学的にそれを行う方法を見つけることができなかったようで、検索で何かを見つけることもできませんでした。何か案は？

4

4 に答える 4

3

これが仕事をする一つの方法です。間違いなく可能な限り最も効率的ではありませんが、とにかく素晴らしいです。これは、1 つだけが残りの部分と異なる限り (明らかに単位桁で)、任意の数の入力に対して機能します。

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

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

    std::sort(std::begin(n), std::end(n),
        [](int a, int b) { return a%10 < b%10;});

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

編集：別のものを追加することにしました。これはまだ@Riciの（非常に素晴らしい）ソリューションよりも多くの比較を行いますが、少なくとも線形です（元のデータを再配置しません）：

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

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

    auto pos = std::adjacent_find(std::begin(n), std::end(n),
        [](int a, int b) { return a%10 != b%10; });

    if (pos != std::begin(n))
        std::cout << pos[1];
    else
        std::cout << n[n[1]%10 != n[2]%10];
}
于 2013-02-07T05:29:32.413 に答える
3

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)];
}
于 2013-02-07T06:58:30.227 に答える
2

どうぞ... :p

任意の数の入力に対して機能します...さらに、それらがすべて同じかどうかを検出します。

#include <iostream>
int main() {
   int a[] = {4,14,24,34,27,94};
   // assume a has more than 2 elements, otherwise, it makes no sense
   unsigned ri = 0;

   if (a[1]%10 == a[0]%10) {
      for (ri = 2; (ri < sizeof(a)/sizeof(a[0])) && (a[ri]%10 == a[0]%10); ri++);
   } else if (a[2]%10 == a[0]%10)
      ri = 1;

   if (ri < sizeof(a)/sizeof(a[0]))
      std::cout << "weird number is a["<< ri <<"] = "<<a[ri] << std::endl;
   else
      std::cout<<"they're all the same" << std::endl;
   return 0;
}

実際の作業は次のとおりです。

   if (a[1]%10 == a[0]%10) {
      for (ri = 2; (ri < sizeof(a)/sizeof(a[0])) && (a[ri]%10 == a[0]%10); ri++);
   } else if (a[2]%10 == a[0]%10)
      ri = 1;

たったの4行！:p

ライブワークスペースでチェックしてください

実行時間は max(1,[例外の場所 #]) で、これは O(n) で、n は a のサイズです。

于 2013-02-07T04:41:46.357 に答える
2

%演算子を使用して単位桁の値を取るプログラムを作成します

void check ()
{
    int i, changeIndex =0;
    for ( i = 0; i < 5; i++)
    {
        for (int k = 0; k < 5; k++)
        {
            if (a[i]%10 == a[k]%10)
            {
                changeIndex++;        
            }
        }
        if (changeIndex != 4)
        {
             break;
        }
        changeIndex = 0;

    }
    cout<<a[i];
}

これは、カウントが 5 の場合に機能し、数字の 1 つだけが異なる単位桁数を持つ場合に機能します。

于 2013-02-07T04:06:09.657 に答える