数组中邻近最近的相同数字-算法

数组中相邻最近的相同数字-算法
数组中相邻最近的相同数字-算法，例如{1,2,3,4,5,1,2,2,5},最近的相同数字是2，求解答，此问要求算法优化，最好附上代码及注释，冒泡排序不必说

------解决方案--------------------
我的想法：用一个数组（Q）来存放以读取的数．和该数在数组中的位置．．．

struct A
{
int Value;
int index;
}
如果当前数值在　Q数组中，则判断位置差多少，在和上一次找到了的位置差比较是否要替换，当遍历完成或位置差为１时就结束吧．．
------解决方案--------------------
这个好像也是冒泡算法的变体，表示　无住，　坐等高手．．．

C/C++ code


#include <iostream>
#include <string>
#include <vector>
using namespace std;


int main()
{
    const int max_array = 10;
    int B[max_array] = {2, 4, 5, 8, 2, 1, 2, 5, 4, 7};
    int weizhi = max_array;
    int value = 0;

    for (int i = 0; i < max_array; i++)
    {
        for (int j = i + 1; j < max_array; j++)//从当前数值　的下一个开始查找
        {
            if (B[i] == B[j])//是否找到了　
            {
                if (weizhi > (j - i - 1))//判断位置差是否符合
                {
                    weizhi = j - i - 1;//修改数据
                    value = B[i];
                    break;//向下遍历所以不用遍历全部
                }
            }
             
        }
    }
    cout<< "位置差：" << weizhi << "数值：" << value << endl;

    return 0;
}

------解决方案--------------------
用map记录最后一次出现的位置

C/C++ code

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;


int main()
{
    const int max_array = 10;
    int B[max_array] = {2, 4, 5, 8, 2, 1, 2, 5, 4, 7};
    map<int, int> pos;
    int v = -1, mind = 1000000000, d;
    for (int i = 0; i < max_array; i++)
    {
        if (pos.count(B[i]) > 0)
        {
            d = i - pos[B[i]] - 1;
            if (d < mind)
            {
                mind = d;
                v = B[i];
            }
        }
        pos[B[i]] = i;
    }

    cout << "The min dist is: " << mind << ", value is: " << v << endl;
}

数组中邻近最近的相同数字-算法

相关推荐