解题总结-2-去重排序

明明的随机数

https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

解题思路

题目的意思很简单，就是对一组数据进行去重排序，得到结果。有三个思路，关键在与去重和排序的顺序

先去重，后排序
首先可以将数据存放在一个集合中或者，这样重复的数据就被筛掉，只保留一个。然后可以使用排序算法对这些数据排序。
将所有的数据排序，然后只输出第一个数，或者在数组/列表中删重复的元素
排序和去重同时进行
（1）使用二叉排序树，在建立的时候忽略掉已有的元素
（2）使用hash表，因为数据的范围不是太大，可以建立一张下标为1-1000的hash表，存放的时候已经有序，只需要从下标1开始输出所有非0元素
下面实现以上的解题思路，不一定是完整的解题代码

算法实现

1. 先去重后排序（python3）

while True:
    len = int(input)
    nuset = set()
    for i in range(a): nuset.add(int(input))
    for i in sorted(nuset): print(i)

如果数据已经存储在一个列表中，python有许多封装好的方法可以使用，如果要详细了解可以参考Python列表去重的几种方法
实际上先去重后排序的思路，关键在与用什么样的算法和数据结构来去重，查找的元素是否在记录中，可以是简单的遍历查找，二分查找，也可以使用集合这样高级的数据结构

while True:
    mylist = list()
    len = int(input)
    for i in range(a):
        nu = int(input)
        //使用遍历查找
        if nu not in mylist: mylist.append(nu)
    for i in sorted(mylist): print(i)

2. 先排序后去重（python3）
简单地实现排序去重的思路，实际上如果数据从终端输入，没有必要先存放在数组中排好序，再去掉重复元素。如果是自己实现排序算法，可以在排序算法中实现去重，这就是第三种思路了。
那么这里假定数据存放在数组mylist中，长度为length

def solution(mylist, length):
    ## sorted(mylist)不会修改mylist
    mylist.sort()
    sav = 0        ## 指向保留的元素的末尾
    cul = sav + 1  ## 指向待筛选的元素
    while cul < length :
        while mylist[cul] == mylist[sav]:
            cul += 1
        sav += 1
        ## 可以直接输出print(mylist[sav])
        mylist[sav] = mylist[cul]
        cul += 1
    mylist = mylist[:length]
    return mylist

3. 边排序边去重
这里主要涉及到的是排序算法，如何在排序的算法中加入去重的功能呢？常用的排序算法有冒泡排序，选择排序，插入排序，shell排序，归并排序，快速排序，堆排序。其中后面4种排序算法是不稳定的，没有想到有改进的方法。冒泡和选择都可以得到最大或者最小值
对与插入排序，有两种改进思路

折半插入排序
在插入之前使用折半查找，看已经排好序的序列中是否包括该元素，再进行插入

// 折半插入排序
int BinInsertSort(int data[], int all)
{
  // 有序序列的长度
  int length = 1 ;
  for(int i = 1; i < all; i++){
      bool ignore = false ;
      int temp = data[i] ;
      int low = 0 ,high = length - 1 ;
      // 使用折半查找算法查找元素的位置
      while(low <= high){
          int mid = (high + low) / 2 ;
          if(temp < data[mid])
              high = mid - 1 ;
          else if(temp > data[mid])
              low = mid + 1 ;
          else{
              // 增加一层相等判断的逻辑
              ignore = true ;
              break ;
          }
      }
      if(ignore == false){
          for(int j = i-1; j >= low; j--)
              data[j+1] = data[j] ;
          length++ ;
          data[low] = temp ;
      }
  }
  return length ;
}

简单插入排序
在简单插入排序中，边插入边判断key值和数组元素的大小关系，因此结束插入后要复原已经插入的部分，这样比较麻烦，因此我想到了二叉排序树，本质上也是一个插入排序，只是数据结构不一样。

// 简单插入排序
void InsertSort(int data[], int all)
{
    int i, j ;
    for(i = 1; i < all; i++){
        int temp = data[i] ;
        ## 不好改进
        for(j = i - 1; j >= 0 && temp < data[j]; j--)
            data[j+1] = data[j] ;
        data[j+1] = temp ;
    }
}

二叉排序是一个递归定义，
(1) 如果左右孩子不全为空，节点的左孩子的值小于当前节点，节点的右孩子大于当前节点
(2) 节点的左孩子和右孩子也是二叉排序树
而且中序遍历二叉排序树可以得到一个有序序列，为简单起见，以下的二叉排序树的节点数据为整型，只实现了中序遍历和插入函数

#include <iostream>
using namespace std ;

// 节点定义
typedef struct Node{
    int key ;
    struct Node *lchild ;
    struct Node *rchild ;
} Node ;

// 二叉排序树
class SortTree{
private:
    Node *root ;

    void Insert(Node *&p, int k) ;
    void Free(Node *&p) ;
    void InOrder(Node *p);

public:
    SortTree() {root = nullptr ;}
    SortTree(int a[], int n) ;
    ~SortTree() ;
    // 公有接口
    void Insert(int fkey) ;
    void InOrder();
} ;
// 析构函数
void SortTree::Free(Node *&p)
{
    if(p == nullptr)
        return ;
    Free(p->lchild) ;
    Free(p->rchild) ;
    delete p ;
}
SortTree::~SortTree()
{
    Free(root) ;
}

// 构造函数
SortTree::SortTree(int a[], int n)
{
    root = nullptr ;
    for (int i = 0; i < n; ++i) {
        Insert(root, a[i]) ;
    }
}
// 插入函数
void SortTree::Insert(Node *&p, int k)
{
    if(p == nullptr){
        p = new Node ;
        p->key = k ;
        p->lchild = p->rchild = nullptr ;
    }else{
        if(k < p->key)
            Insert(p->lchild, k) ;
        else if(k > p->key)
            Insert(p->rchild, k) ;
        // 如果待插入的元素和与节点元素相等，则不处理，起到了去重的效果
    }
}
void SortTree::Insert(int k)
{
    Insert(root, k) ;
}
// 中序遍历
void SortTree::InOrder(Node *p)
{
    if(!p) return ;
    InOrder(p->lchild) ;
    std::cout << p->key << std::endl ;
    InOrder(p->rchild) ;
}
void SortTree::InOrder()
{
    InOrder(root) ;
}

// 主函数
int main(int argc, char *argv[])
{
    int len = 0 ;
    while(cin >> len){
        SortTree sol ;
        for(int i = 0; i < len; i++){
            int nu ;
            cin >> nu ;
            sol.Insert(nu) ;
        }
        sol.InOrder() ;
    }
    return 0;
}

达到边去重边排序的效果还有一种方法就是使用hash表，这里要求元素的最大值不太大。原题中要求最大值为1000，那么我可定义一个大小为1001(不使用下标0)的整型或者bool型数组，将数组初始化为0(false)，每读取一个元素将对应的位置置为1(true)。在读完输入流后，可以按顺序输出所有的非0元素的下标，也就是其值。顺序表的下标是有序，用hash的思想将对应的元素放置到相应的位置，就是说在存放的过程中保持有序。
下面是代码实现：

#include <iostream>
using namespace std ;
int main(int argc, char *argv[])
{
    int len = 0 ;
    while(cin >> len){
        int num[1001] = {0} ; // 自动初始化为0
        for(int i = 0; i < len; i++){
            int temp ;
            cin >> temp ;
            // 这里也可以记录重复数字出现的次数
            if(num[temp] == 0) num[temp] = 1 ;
        }
        for(int i = 1; i <= 1000; i++){
            if(num[i] != 0)
                cout << i << endl ;
        }
    }
    return 0;
}