从排序数组中删除重复

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; 
    } 
}