一道google topcoder真题

Problem Statement
????
We have a sequence of integers, and we would like to remove all duplicate elements from this sequence. There may be multiple ways to perform this task. For example, given the sequence { 1, 2, 1, 3 }, we could end up with either { 1, 2, 3 } or { 2, 1, 3 } as the remaining sequence, depending on which duplicate 1 we remove from the original sequence. For this problem, we want to return the lexicographically first of of all possible remaining sequences. A sequence S1 comes before sequence S2 lexicographically if and only if S1 has a smaller value than S2 at the lowest index at which the two sequences differ (so, for example, { 1, 2, 3 } comes before { 2, 3, 1 }).
You will be given a int[] sequence. Return a int[] containing the sequence after all the duplicates are removed. See the examples for further clarification.
Definition
????
Class:
HardDuplicateRemover
Method:
process
Parameters:
int[]
Returns:
int[]
Method signature:
int[] process(int[] sequence)
(be sure your method is public)
????

Constraints
-
sequence will have between 1 and 50 elements, inclusive.
-
Each element of sequence will be between 1 and 1000, inclusive.
Examples
0)

????
{5, 6, 5, 1, 6, 5}
Returns: {1, 6, 5 }
There are six different ways to remove duplicates (remaining numbers are marked by '*'):
{ *5, *6, 5, *1, 6, 5},
{ *5, 6, 5, *1, *6, 5},
{ 5, *6, *5, *1, 6, 5},
{ 5, 6, *5, *1, *6, 5},
{ 5, *6, 5, *1, 6, *5},
{ 5, 6, 5, *1, *6, *5}.

The last variant is the lexicographically first.
1)

????
{3, 2, 4, 2, 4, 4}
Returns: {3, 2, 4 }

2)

????
{6, 6, 6, 6, 6, 6}
Returns: {6 }

3)

????
{1, 3, 2, 4, 2, 3}
Returns: {1, 2, 4, 3 }

4)

????
{5, 4, 1, 5}
Returns: {4, 1, 5 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

 
/* 
 * File:   main.cpp
 * Author: luo
 *
 * Created on June 24, 2010, 11:10 PM
 */

#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include "testhead.h"

using namespace std;

std::vector<int>::const_iterator vector_index(const std::vector<int> &iv, int token ) {
    for(std::vector<int>::const_iterator it=iv.begin(); it<iv.end(); it++) {
        if(token == *it) {
            return it;
        }
    }
    return iv.end()+1;

}
class HardDuplicateRemover
{
public:
   std::vector<int> process(const std::vector<int> & iv) {
       std::vector<int> result;       
       for(
               std::vector<int>::const_iterator it=iv.begin();
               it!=iv.end();
               ++it
       ) {
           std::vector<int>::const_iterator index_at = vector_index(result, *it);

           if (index_at > result.end() ) {
               result.push_back(*it);
           }
           else if(index_at < result.end()) {
               if(*index_at > *(index_at+1)) {
                   int b = index_at - result.begin();
                   result.erase(result.begin() + b);
                   result.push_back(*it);
               }
           }
           else { // ==
               
           }
       }
       return result;
  }
};

/*
 * 
 */
int main(int argc, char** argv) {
    HardDuplicateRemover h;
    int arr[] ={5, 4, 1, 5};
    std::vector<int> iv(arr, arr + 4);

    cout << "{";
    for(std::vector<int>::const_iterator i = iv.begin();
            i<iv.end();
            ++i) {
        cout << *i << ",";
    }
    cout << "}" << endl;
    
    std::vector<int> rs = h.process(iv);
    cout << endl << "{";
    for(std::vector<int>::const_iterator i = rs.begin();
            i<rs.end();
            ++i) {
        cout << *i << ",";
    }
    cout << "}" << endl;
    return 0;
}

Posted by rollenc