循环/方法太慢

Question

我目前正在处理来自hackerrank的一个问题，而且我正在考虑我的问题的时间限制。我似乎无法弄清楚为什么。

输出具有最小差异的数字对。如果有多个对，则按升序输出所有对，全部在同一行（连续），每对数之间只有一个空格。如果有一对数字位于两对中，则打印两次（参见样本案例＃3以获得解释）。

输入 数量包含所有由空格隔开的字符串的元素

样品：

4 
5 4 3 2 

输出：

2 3 3 4 4 5 

测试情况下，我失败上具有100000级的输入。我计算了我的代码，并且我的代码中最慢的部分是函数closest中的循环。我原本有一个向量，然后在列表后使用std：sort。然后我尝试使用multiset而不是调用std :: sort来尝试并提高我的性能。它仍然没有通过测试。有关如何改进closest或addPair方法中循环的任何想法？

#include <iostream> 
#include <set> 
#include <utility> 
#include <cmath> 
#include <string> 
#include <algorithm> 
#include <ctime> 

#define NUMBER 10000 
double diffclock(clock_t clock1, clock_t clock2) 
{ 
    double diffticks = clock1 - clock2; 
    double diffms = (diffticks)/(CLOCKS_PER_SEC/NUMBER); 
    return diffms; 
} 

class ClosestPair 
{ 
    private: 
     long _distance; 
     const char UNSET = -1; 
     std::multiset<int> _list; 
     long getDistance(const int number1, const int number2) const; 

    public: 
     ClosestPair(); 
     ~ClosestPair(); 
     void addPair(const int number1, const int number2); 
     const std::multiset<int>& getList() const; 
     const std::string toString() const; 
     void sort(); 

}; 

ClosestPair::ClosestPair() 
{ 
    _distance = UNSET; 
} 

ClosestPair::~ClosestPair() 
{ 
} 

void ClosestPair::addPair(const int number1, const int number2) 
{ 
    long distance = getDistance(number1, number2); 

    if(distance < _distance || _distance == UNSET) 
    { 
     _list.clear(); 
     _distance = distance; 
     //std::pair<int, int> newPair(number1, number2); 
     //_list.push_back(newPair); 
     _list.insert(number1); 
     _list.insert(number2); 
    } 
    else if(distance == _distance) 
    { 
     _list.insert(number1); 
     _list.insert(number2); 
     //std::pair<int, int> newPair(number1, number2); 
     //_list.push_back(newPair); 
    } 
} 

inline long ClosestPair::getDistance(const int number1, const int number2) const 
{ 
    return std::abs(number1 - number2); 
} 

const std::multiset<int>& ClosestPair::getList() const 
{ 
    return _list; 
} 

const std::string ClosestPair::toString() const 
{ 
    std::string allPairs; 

    for(auto iterator = _list.begin(); iterator != _list.end(); iterator++) 
    { 
     allPairs += std::to_string(*iterator); 
     allPairs += " "; 
     //allPairs += std::to_string(iterator->second); 
     //allPairs += " "; 
    } 

    if(allPairs.size() > 0) 
    { 
     allPairs.substr(0, allPairs.size() - 1); 
    } 

    return allPairs; 
} 

void ClosestPair::sort() 
{ 
    //std::sort(_list.begin(), _list.end()); 
} 

void closest(int* array, int size) 
{ 
    ClosestPair closestPairs; 

    clock_t begin = clock(); 
    for(int i = 0; i < size; i++) 
    { 
     for(int j = i + 1; j < size; j++) 
     { 
      closestPairs.addPair(array[i], array[j]); 
     } 
    } 
    clock_t end = clock(); 
    std::cout << "AddPair time: " << diffclock(end, begin) << " ms." << std::endl; 

    //closestPairs.sort(); 
    begin = clock(); 
    std::cout << closestPairs.toString(); 
    std::cout << "toString time: " << diffclock(end, begin) << " ms." << std::endl; 
    end = clock(); 
} 

int main() 
{ 
    int sizeOfList; 
    std::string allNumbers; 
    std::cin >> sizeOfList >> std::ws; 
    std::getline(std::cin, allNumbers); 

    size_t position = 0; 
    size_t nextPosition = 0; 
    int count = 0; 
    int array[sizeOfList]; 

    clock_t begin = clock(); 
    do 
    { 
     position = nextPosition; 
     nextPosition = allNumbers.find(' ', position + 1); 
     if(position > 0) 
      position++; 
     array[count] = atoi(allNumbers.substr(position, nextPosition - position).c_str()); 
     count++; 
    } 
    while(nextPosition != std::string::npos); 
    clock_t end = clock(); 
    std::cout << "Tokenize time: " << diffclock(end, begin) << " ms." << std::endl; 

    closest(array, sizeOfList); 
    return 0; 
} 

Answer 1

// requires [b,e) is sorted: 
template<typename Iterator> 
std::vector<Iterator> find_close_pairs(Iterator b, Iterator e){ 
    if (b==e || std::next(b) == e) return {}; 
    std::vector<std::size_t> retval = {0}; 
    auto old = *std::next(b) - *b; 
    for(auto it = std::next(b); std::next(it) != e; ++it) { 
    auto delta = *std::next(it) - *it; 
    if (delta < old) { 
     retval.clear(); 
     old = delta; 
    } 
    if (delta <= old) { 
     retval.push_back(it); 
    } 
    } 
    return retval; 
} 
// requires: iterators are writable. Sorts range. Faster with random access: 
template<typename Iterator> 
std::vector<std::pair<int,int>> solve(Iterator b, Iterator e) { 
    std::sort(b, e); 
    auto close_pairs_indexes = find_close_pairs(b, e); 
    std::vector<std::pair<int,int>> retval; 
    retval.reserve(close_pairs_indexes.size()); 
    for(auto it:close_pairs_indexes) { 
    retval.push_back({*it, *std::next(it)}); 
    } 
    return retval; 
} 
// requires: numbers is a container, not a C array: 
template<typename Container> 
std::vector<std::pair<int,int>> solve(sContainer numbers) { 
    using std::begin; using std::end; 
    return solve(begin(numbers), end(numbers)); 
} 

是C++ 11并可能有错别字，但应该这样做。在手机上，代码过于简洁。

Answer 2

如果我正确理解你的问题，你也可以使用multimap。该映射的键/值是int/pair（int，int）。

一次检查您的排序列表中的2个数字。计算两个数字之间的差异。这种差异成为地图中的一个关键值，这两个数字是你用来提出差异的两个数字。

完成之后，您可以保证最小的差异在地图的开头，因为地图使用<对按键进行排序。你现在有最小的差异加上导致差异的那对数字的信息。

例如：

#include <map> 
#include <vector> 
#include <algorithm> 

typedef std::multimap<int, std::pair<int, int>> IntMap; 
typedef std::vector<int> IntVect; 

void getDifferences(const IntVect& intVect, IntMap& theMap) // assume intVect is  sorted 
{ 
    theMap.clear(); 
    if (intVect.size() < 2) 
     return; 

    size_t nItems = intVect.size(); 
    for (size_t i = 0; i < nItems - 1; ++i) 
    { 
     int num1 = intVect[i+1]; 
     int num2 = intVect[i]; 
     int diff = num1 - num2 
     theMap.insert(std::make_pair(diff, std::make_pair(num2, num1))); 
    } 
} 

int main() 
{ 
    int Test[] = { 3, 4, 2, 7, 1, 11 }; 
    IntVect testV(Test, Test + sizeof(Test)/sizeof(Test[0])); 
    std::sort(testV.begin(), testV.end()); 
    IntMap myMap; 
    getDifferences(testV, myMap); 
} 

注意，要同时建立地图来完成的最小从来没有检查。有点让这个“安全”，但其他非映射答案更可能执行得更快。