2嵌套for循環推入一個向量，試圖不重複push_back值

Question

我有兩個嵌套for循環推入到一個數組中，我不想在推回時造成重複。下面是一些代碼，使我的問題更加清晰：

int TARGET = 180; 
    vector<int> dataSet; 
    vector<Sublist> choices; 

    dataSet.push_back(20); dataSet.push_back(12); dataSet.push_back(22); 
    dataSet.push_back(15); dataSet.push_back(25); 
    dataSet.push_back(19); dataSet.push_back(29); 
    dataSet.push_back(18); 
    dataSet.push_back(11); dataSet.push_back(13); dataSet.push_back(17); 
    choices.push_back(Sublist(&dataSet)); 


    numSets = 1; 
    foundPerfect = false; 
    for (k = 0; k < dataSet.size(); k++) 
    { 
     for (j = 0; j < numSets; j++) 
     { 
     if (choices[j].getSum() + dataSet[k] < TARGET) 
     { 
      choices.push_back(choices[j].addItem(k)); 
      cout << numSets << endl; 
      numSets++; 
     } 
     if (choices[j].getSum() + dataSet[k] == TARGET) 
     { 
      cout << "0" << endl; 
      foundPerfect = true; 
      max = j; 
      break; 
     } 
     } 
    } 

類定義：

class Sublist 
{ 
public: 
    Sublist(vector<int> *orig = NULL) 
     : sum(0), originalObjects(orig) { } 
    Sublist addItem(int indexOfItemToAdd); 
    void showSublist() const; 
    int getSum() const { return sum; } 

private: 
    int sum; 
    vector<int> *originalObjects; 
    vector<int> indices; 
}; 

Sublist Sublist::addItem(int indexOfItemToAdd) 
{ 
    Sublist passSublist; 

    passSublist = *this; 

    //new sum being added 

    cout << "sum added: " << (*originalObjects)[indexOfItemToAdd] << endl; 
    passSublist.sum = sum + (*originalObjects)[indexOfItemToAdd]; 


    //new index being added into indices 
    //passSublist.indices.push_back((*originalObjects)[indexOfItemToAdd]); 
    passSublist.indices.push_back(indexOfItemToAdd); 
    //cout << passSublist.sum << endl; 
    return passSublist; 
} 
void Sublist::showSublist() const 
{ 
    vector<int>::const_iterator vIter; 
    if (indices.empty()) 
     cout << "array[" << "0" << "] = " << "EMPTY"; 
    for (vIter = indices.begin(); vIter != indices.end(); vIter++) 
    { 
     cout << "array[" << *vIter << "] = " << (*originalObjects)[*vIter] << ", "; 
     //cout << this->sum << endl; 
    } 
} 

目前我的選擇矢量充滿重複的指標。我發現完美之前或等於使用單獨的語句在我的程序與結果是最終目標：

array[0] = 20, array[0] = 20, array[0] = 20, array[0] = 20, array[0] = 20, array 
[0] = 20, array[0] = 20, array[1] = 12, array[1] = 12, array[3] = 15, sum:179 

數組[0]應該只出現一次。與[1]相同。任何想法如何解決這個請好嗎？

如果有人想測試它，這是一個完全可行的程序。

#include <iostream> 
using namespace std; 

#include <ctime> 
#include <vector> 
#include <cstdlib> 

#include <stdio.h> 


#include <algorithm> 

class Sublist 
{ 
public: 
    Sublist(vector<int> *orig = NULL) 
     : sum(0), originalObjects(orig) { } 
    Sublist addItem(int indexOfItemToAdd); 
    void showSublist() const; 
    int getSum() const { return sum; } 

private: 
    int sum; 
    vector<int> *originalObjects; 
    vector<int> indices; 
}; 

Sublist Sublist::addItem(int indexOfItemToAdd) 
{ 
    Sublist passSublist; 

    passSublist = *this; 

    //new sum being added 

    cout << "sum added: " << (*originalObjects)[indexOfItemToAdd] << endl; 
    passSublist.sum = sum + (*originalObjects)[indexOfItemToAdd]; 


    //new index being added into indices 
    //passSublist.indices.push_back((*originalObjects)[indexOfItemToAdd]); 
    passSublist.indices.push_back(indexOfItemToAdd); 
    //cout << passSublist.sum << endl; 
    return passSublist; 
} 
void Sublist::showSublist() const 
{ 
    vector<int>::const_iterator vIter; 
    if (indices.empty()) 
     cout << "array[" << "0" << "] = " << "EMPTY"; 
    for (vIter = indices.begin(); vIter != indices.end(); vIter++) 
    { 
     cout << "array[" << *vIter << "] = " << (*originalObjects)[*vIter] << ", "; 
     //cout << this->sum << endl; 
    } 
} 

int main() 
{ 
    int TARGET = 180; 
    vector<int> dataSet; 
    vector<Sublist> choices; 
    vector<Sublist>::iterator iter, iterBest; 
    int k, j, numSets, max, masterSum; 
    bool foundPerfect; 

    dataSet.push_back(20); dataSet.push_back(12); dataSet.push_back(22); 
    dataSet.push_back(15); dataSet.push_back(25); 
    dataSet.push_back(19); dataSet.push_back(29); 
    dataSet.push_back(18); 
    dataSet.push_back(11); dataSet.push_back(13); dataSet.push_back(17); 

    choices.clear(); 
    cout << "Target time: " << TARGET << endl; 

    cout << endl; 



    choices.push_back(Sublist(&dataSet)); 
    /* 
    choices.push_back(choices[0].addItem(5)); 
    choices.push_back(choices[1].addItem(2)); 
    choices.push_back(choices[2].addItem(4)); 

    vector<Sublist>::iterator iter, iterBest; 
    int k, j, numSets, max, masterSum; 
    bool foundPerfect; 
    */ 

    vector<int> randIndices; 
    srand(time(NULL) + rand()); 

    numSets = 1; 
    foundPerfect = false; 
    for (k = 0; k < dataSet.size(); k++) 
    { 
     for (j = 0; j < choices.size(); j++) 
     { 
     if (choices[j].getSum() + dataSet[k] < TARGET) 
     { 
      choices.push_back(choices[j].addItem(k)); 
      cout << numSets << endl; 
      numSets++; 
     } 
     if (choices[j].getSum() + dataSet[k] == TARGET) 
     { 
      cout << "0" << endl; 
      foundPerfect = true; 
      max = j; 

      iterBest = choices.begin(); 
      iterBest = iterBest + j; 
      break; 
     } 
     //k++; 
     } 
    } 

    system("pause"); 

    cout << "display" << endl; 

    for (iter = choices.begin(); iter != choices.end(); iter++) 
    { 
     iter->showSublist(); 
     cout << "\n---sublist class sum:" << iter->getSum() << endl << endl; 
     cout << "next sublist class\n" << endl; 
    } 


    vector<Sublist>::iterator best; 
    int highestSum = 0; 
    int highestSumsIndex; 
    for (int q = 0; q < choices.size(); q++) 
    { 
     if ((choices[q].getSum() > highestSum) && (choices[q].getSum() <= TARGET)) 
     { 
     highestSum = choices[q].getSum(); 
     highestSumsIndex = q; 
     } 
    } 
    choices[highestSumsIndex].showSublist(); 
    cout << choices[highestSumsIndex].getSum(); 



    cout << "pause" << endl; 
    std::system("pause"); 
    return 0; 
} 

Answer 1

所以，如果我理解正確的話，你想有沒有重複在indices。有兩個選項：

1. 檢查的元素已經存在：

   if (std::find(passSublist.indices.begin(), passSublist.indices.end(), indexOfItemToAdd) != passSublist.indices.end()) 
       passSublist.indices.push_back(indexOfItemToAdd); 
   

   我不建議這樣做因爲你會較慢插入結束了，因爲你必須遍歷可能首先是整個矢量，這基本上是最壞情況O（n）。

2. 改爲使用std::set。這是一個數據結構，其中沒有重複的，這是以插入順序爲代價的。包括set在你的程序的啓動和更換：

   vector<int> indices; 
   

   有：

   set<int> indices; 
   

   和替換這樣的：

   passSublist.indices.push_back(indexOfItemToAdd); 
   

   有：

   passSublist.indices.insert(indexOfItemToAdd); 
   

   也改變vector<int>::iterator vIter至set<int>::iterator vIter。

   這比選擇1更受歡迎，因爲插入時間是O（log n）。