计算序列中元素的位置

计算序列中元素的位置

         寻找序列中元素的位置，这里序列是有序的。根据序列中元素是否有重复分为无重复序列和有重复序列两种情况。

一、无重复的情况：

我们只考虑升序的情况，降序的情况与此类似，故不作讨论。比如，有以下序列：

3、5、6、8、9、10、15、30、41

         待查找元素为15，其位置为6（3的位置为0，位置从0开始计算），其逆位置为2

         如果待查找元素在序列中不存在，则返回位置-1，逆位置也是-1。

1）顺序查找

         最直观的的方法是顺序查找，程序实现如下：

// 无重复顺序查找
#include <iostream>
#include <vector>
using namespace std;

void no_repeat_order(const vector<int>& seq, int n, int& pos, int& rpos)
{
    pos = rpos = -1;
    for (int i = 0; i != seq.size(); ++i)
    {
        if (n < seq[i])
        {
            break;
        }
        else if (n == seq[i])
        {
            pos = i;
            rpos = seq.size() - pos - 1;
            break;
        }
    }
    
    return;
}

int main()
{
    int a[] = {3, 5, 6, 8, 9, 10, 15, 30, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
     
    int pos = -1, rpos = -1;
    no_repeat_order(seq, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    no_repeat_order(seq, 16, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}

         顺序扫描可以处理无序的情况（注：在本例的顺序查找中，我们仍利用了有序的特性来提高查找效率，但同时也增加了判断的情况：if seq[i] < n break），针对这种有序的情况，我们可以采用二分的方法来提高查找的速度，顺序扫描的时间复杂度为O(N)，二分查找的时间复杂度为O(logN)。

2）二分查找

// 无重复二分查找
#include <iostream>
#include <vector>
using namespace std;

void no_repeat_binary(const vector<int>& seq, int n, int& pos, int& rpos)
{
    pos = rpos = -1;
    int left = 0, right = seq.size() - 1;
    int middle = 0;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (n == seq[middle])
        {
            pos = middle;
            rpos = seq.size() - pos - 1;
            break;
        }
        else if (n < seq[middle])
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }
    
    return;
}

int main()
{
    int a[] = {3, 5, 6, 8, 9, 10, 15, 30, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
     
    int pos = -1, rpos = -1;
    no_repeat_binary(seq, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    no_repeat_binary(seq, 16, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}

         以上是对无重复序列两种查找元素方式的讨论，分别是顺序扫描和二分查找，时间复杂度分别是O(N)和O(logN)。下面我们讨论有重复序列的情况。

一、有重复的情况

在这里我们只考虑非降序序列，非升序的情况与此类似，故不作讨论。比如，有以下序列：

3、5、6、8、9、9、10、15、15、15、30、30、41、41

         假如待查找元素为15，则位置为7，逆位置为2。

         假如待查找元素为41，则位置为12，逆位置为0。

         假如待查找元素不存在于序列中，则位置为-1，逆位置为-1。

1）顺序查找

// 有重复顺序查找
#include <iostream>
#include <vector>
using namespace std;

void repeat_order(const vector<int>& seq, int n, int& pos, int& rpos)
{
    pos = rpos = -1;
    for (int i = 0; i != seq.size(); ++i)
    {
        if (n < seq[i])
        {
            break;
        }
        else if (n == seq[i])
        {
            pos = i;
            while (i < seq.size() && n == seq[i])
            {
                ++i;
            }
            rpos = seq.size() - i;
            break;
        }
    }
    
    return;
}

int main()
{
    int a[] = {3, 5, 6, 8, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
     
    int pos = -1, rpos = -1;
    repeat_order(seq, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_order(seq, 41, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_order(seq, 9, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_order(seq, 18, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}

2）二分查找

         考虑到这是一个有序的序列，我们可以利用二分查找，但是由于序列中存在有重复的元素，所以我们在查找位置的时候需要找到第一个出现的位置，在求解逆位置的时候需要找到最后一个出现的位置。

         第一种方式是首先利用二分的方式，找到一个匹配的元素，然后根据这个数进行向前或向后扫描，得到位置和逆位置。这种方法的时间复杂度最好是O(logN)，但是在最坏的情况下是O(N)，最坏的情况就是待查找元素出现次数很多的情况。

2.1）先二分后扫描

         首先将先二分后扫描的实现如下：

// 有重复先二分后扫描
#include <iostream>
#include <vector>
using namespace std;

void repeat_binary_1(const vector<int>& seq, int n, int& pos, int& rpos)
{
    pos = rpos = -1;
    int left = 0, right = seq.size() - 1;
    int middle = 0;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (n == seq[middle])
        {
            int i = middle, j = middle;
            while (i >= 0 && n == seq[i])
            {
                --i;
            }
            pos = i + 1;
            while (j < seq.size() && n == seq[j])
            {
                ++j;
            }
            rpos = seq.size() - j;
            break;
        }
        else if (n < seq[middle])
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }
    
    return;
}

int main()
{
    int a[] = {3, 5, 6, 8, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
     
    int pos = -1, rpos = -1;
    repeat_binary_1(seq, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_1(seq, 41, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_1(seq, 9, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_1(seq, 18, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}

2.2）完全二分

         为了保证在最坏情况下也是O(logN)的时间复杂度，我们采用完全二分的方式进行查找。实现如下：

// 无重复完全二分
#include <iostream>
#include <vector>
using namespace std;

void repeat_binary_2(const vector<int>& seq, int n, int& pos, int& rpos)
{
    pos = rpos = -1;
    if (n < seq[0] || n > seq[seq.size()-1])
    {
        return;
    }
    
    int left = 0, right = seq.size() - 1;
    int middle = 0;
    // find pos
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (n == seq[middle])
        {
            if (middle > left && n == seq[middle-1])
            {
                right = middle - 1;
                continue;
            }
            else
            {
                pos = middle;
                break;
            }
        }
        else if (n < seq[middle])
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }
    
    // find rpos
    left = 0;
    right = seq.size() - 1;
    middle = 0;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (n == seq[middle])
        {
            if (middle < right && n == seq[middle+1])
            {
                left = middle + 1;
                continue;
            }
            else
            {
                rpos = seq.size() - middle - 1;
                break;
            }
        }
        else if (n < seq[middle])
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }
    
    return;
}

int main()
{
    // int a[] = {3, 5, 6, 8, 9, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41, 41};
    // int a[] = {15, 15, 15};
    int a[] = {3, 5, 6, 8, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
     
    int pos = -1, rpos = -1;
    repeat_binary_2(seq, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_2(seq, 41, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_2(seq, 9, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    repeat_binary_2(seq, 18, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}

三、总结

         以上讨论了无重复、有重复有序序列的元素查找方法。其中无重复序列的元素查找分为顺序查找和二分查找。

有重复序列的查找也分为顺序查找和二分查找。由于“有重复”这个特点，在查找元素第一次出现的位置和最后一次出现的位置时，二分查找分为两种方式，一种是先二分后顺序扫面，这种方法最好的情况是O(logN)的时间复杂度，但是最差情况下的时间复杂度为O(N)，所谓最差的情况就是序列中全是一个元素，或者该元素出现次数很多，另外业余元素在整个序列中的分布有关。第二种二分方法是完全二分，在找到元素后，进一步采用二分方法进行搜寻，直至找到第一次出现和最后一次出现的位置为止。

         另外，在查找不是太频繁的情况下，可以采用上述中的二分方法进行查找。但是如果序列中如果元素较多，而且查找很频繁时，最好的方法是先对序列做一个预处理工作，针对每个元素建立一个<元素-位置>哈希表，这样在需要查询元素位置时，可以直接对其进行O(1)的查找。当然这种方法只能适用于序列表固定不变的情况，如果序列表有修改，需要对哈希表进行修改。

         下面给出一种简易的实现，这里没有采用哈希的方式实现<元素-位置>，而是使用的STL种的MAP，所以查询的时间复杂度不是O(1)，而是O(logN)。另外，我们这里讨论的是有重复的序列（注意，有重复序列的处理方式涵盖了无重复的情况）。

         程序实现如下：

// 有重复预处理
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct position
{
    int pos;
    int rpos;
};

void prepro_norepeat(const vector<int>&seq, map<int, position>& hash)
{
    // seq 是有序的
    // seq 是不重复的预处理
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        hash[seq[i]].pos = i;
        hash[seq[i]].rpos = seq.size() - i - 1;
    }
    return;
}

void prepro(const vector<int>& seq, map<int, position>& hash)
{
    // seq 是有序的
    // seq 是重复的预处理
    if (seq.empty())
    {
        return;
    }
    int p = seq[0];
    int q = p;
    hash[seq[0]].pos = 0;
    hash[seq[0]].rpos = seq.size() - 0 - 1;
    
    for (vector<int>::size_type i = 1; i != seq.size(); ++i)
    {
        p = seq[i];
        if (p == q)
        {
            hash[seq[i]].rpos = seq.size() - i - 1;
        }
        else
        {
            hash[seq[i]].pos = i;
            hash[seq[i]].rpos = seq.size() - i - 1;
            q = p;
        }
    }
}

void find_pos(const map<int, position>& hash, int n, int& pos, int& rpos)
{
    // 查找函数
    pos = rpos = -1;
    map<int, position>::const_iterator cit = hash.find(n);
    if (cit != hash.end())
    {
        pos = cit->second.pos;
        rpos = cit->second.rpos;
    }
    return;
}

int main()
{
    // int a[] = {3, 5, 6, 8, 9, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41, 41};
    // int a[] = {15, 15, 15};
    int a[] = {3, 5, 6, 8, 9, 9, 10, 15, 15, 15, 30, 30, 41, 41};
    vector<int> seq(a, a+sizeof (a)/sizeof (*a));
    for (vector<int>::size_type i = 0; i != seq.size(); ++i)
    {
        cout << seq[i] << ' ';
    }
    cout << endl << endl;
    
    map<int, position> hash;
    prepro(seq, hash);
    
    int pos = -1, rpos = -1;
    find_pos(hash, 15, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    find_pos(hash, 41, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    find_pos(hash, 9, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    find_pos(hash, 18, pos, rpos);
    cout << pos << endl;
    cout << rpos << endl;
    
    system("PAUSE");
    return 0;
}