從排序數組中刪除重複

Question

我有這段代碼，我一直在努力了幾個小時，現在試圖找出如何在插入排序過程中實現刪除排序數組中的重複項。我試圖做到這一點，而不必重新編寫整個程序，但隨着我的進步，似乎我可能只需從頭開始，但在此之前我希望看看是否可以使用代碼來完成此操作下面。

現在的問題是，我怎樣才能去除重複排序的數組之前，把它放回到一個文件？

#include <iostream> 
#include <fstream> 
#include <iomanip> 
#include <algorithm> 
#include <vector> 
using std::cout; 
using std::endl; 
using namespace std; 

//sort into an array using insertion sort 
//getis info from file "numbers.txt" 
//and prints the sorted numbers into "sorted_numbers.txt" 
void insertSort(int a[], int length) 
{ 
    int i, j, value; 
    int old = 0; 
    bool first = true; 

    for(i = 1; i < length; i++) 
    { 
     if(first || old != a[i]) 
     { 
      old = a[i]; 
      first = false; 

      value = a[i]; 
      for (j = i - 1; j >= 0 && a[j] > value; j--) 
      { 
       a[j + 1] = a[j]; 
      } 
     } 
     a[j + 1] = value; 
    } 
} 

//prints out the array in 'Run I/O' 
void printarray(int arg[], int length) 
{ 
    for(int n =0; n<length; ++n) 
     cout << arg[n] << ' '; 
    cout << '\n'; 
} 

int main() 
{ 
    std::ifstream in; 
    std::ofstream out; 

    int N = 10; 
    int n = 0; 
    int k; 
    int* a = new int(N); 

    //opens the file "numbers.txt" if it exit 
    //gets the chars from file and sorts them 
    //into array "a[n]" 
    in.open("numbers.txt"); 
    if(!in.is_open()) 
    { 
     std::cout << "File could not be opened FILE NOT FOUND." << std::endl; 

     //creates the a new file to be read from if numbers.txt does 
     //not already exist and put numbers inside of it 
     //to be sorted with the InsertSort function 
     out.open("numbers.txt"); 
     out << "1" << endl; 
     out << "3" << endl; 
     out << "7" << endl; 
     out << "4" << endl; 
     out << "2" << endl; 
     out << "7" << endl; 
     out << "6" << endl; 
     out << "9" << endl; 
     out << "5" << endl; 
     out << "2" << endl; 

     out.close(); 

     //opens the new numbers.txt file and puts the 
     //numbers into an array to be sorted 
     in.open("numbers.txt"); 

     //runs through the items in the file and 
     //puts them into an array 
     int x; 
     while(in >> x) 
     { 
      a[n] = x; 
      n++; 
     } 

     printarray(a,10); 
     std::cout << "Read " << n << " integers from the file." << std::endl; 

     //sorts the array from when it was read 
     //to the new insertion sort array 
     insertSort(a,n); 

     std::cout << "Integers are sorted" << std::endl; 

     //writes/creates the new sorted array to a new file 
     //called "sorted_numbers.txt" 
     out.open("sorted_numbers.txt"); 
     for(k = 0;k < n;k++) 
      out << a[k] << std::endl; 
      printarray(a,10); 
     out.close(); 

     delete[] a; 

     in.close(); 
    } 
    else 
    { 
     int x; 
     while(in >> x) 
     { 
      a[n] = x; 
      n++; 
     } 

     printarray(a,10); 
     std::cout << "Read " << n << " integers from the file." << std::endl; 

     insertSort(a,n); 

     std::cout << "Integers are sorted" << std::endl; 

     //writes/creates the new sorted array to a new file 
     //called "sorted_numbers.txt" 
     out.open("sorted_numbers.txt"); 
     for(k = 0;k < n;k++) 
      out << a[k] << std::endl; 
      std::cout << n << " integers stored to the file." << std::endl; 
      printarray(a,10); 
     out.close(); 

     delete[] a; 
    } 
    return 0; 
} 

Answer 1

使用algorithm圖書館和std::vector

#include <algorithm> 
#include <vector> 
#include <fstream> 

int main() 
{ 
    std::vector<int> v; 
    { 
    std::ifstream is("numbers.txt"); 
    for (int i; is >> i;) 
     v.push_back(i); 
    } 

    std::sort(v.begin(), v.end()); 
    v.erase(std::unique(v.begin(), v.end()), v.end()); 

    std::ofstream of("sorted_numbers.txt"); 
    for (auto i : v) 
    of << i << '\n'; 

    // Or for non-c++11 
    // for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i) 
    // of << *i << '\n'; 
} 

甚至爲了簡單起見，std::set（矢量版本可以更快，但可能不會多大關係爲您的使用情況）。

#include <algorithm> 
#include <set> 
#include <fstream> 

int main() 
{ 
    std::set<int> s; 
    { 
    std::ifstream is("numbers.txt"); 
    for (int i; is >> i;) 
     s.insert(i); 
    } 

    std::ofstream of("sorted_numbers.txt"); 
    for (auto i : s) 
    of << i << '\n'; 

    // Or for non-c++11 
    // for (std::set<int>::const_iterator i = s.begin(); i != s.end(); ++i) 
    // of << *i << '\n'; 
} 

Answer 2

插入排序進行操作左到右和旋轉的子陣列向右（放置在子陣列左側的最小值），而重複的缺失移位一個子陣列的剩下。作爲替代，我創建並修改了一個「刪除」排序（反向插入排序），該排序從右向左操作並向左旋轉一個子陣列（以將最大值放置在子陣列的右側），以及左移子陣列以刪除重複項。

void deletesort(int a[], int &length) 
{ 
    int i, j, value; 
    if(length < 2) 
     return; 
    for(i = length-2; i >= 0; i--){ 
     value = a[i]; 
     for (j = i+1; j < length; j++){ 
      if(value > a[j]){ 
       a[j-1] = a[j]; 
       continue; 
      } 
      if(value == a[j]){ 
       for(; j < length; j++) 
        a[j-1] = a[j]; 
       length--; 
      } 
      break; 
     } 
     a[j-1] = value; 
    } 
} 

這裏有一個刪除那種不刪除重複：

void deletesort(int a[], int length) 
{ 
    int i, j, value; 
    if(length < 2) 
     return; 
    for(i = length-2; i >= 0; i--){ 
     value = a[i]; 
     for (j = i+1; j < length && value > a[j]; j++) 
      a[j-1] = a[j]; 
     a[j-1] = value; 
    } 
}