Advertisement
Vlad_Yermak0v

Sorting array with O(n) complexity

Sep 8th, 2013
885
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cstdlib>
  6.  
  7. using namespace std;
  8.  
  9. struct vertex {
  10.        int leaf, next[10];
  11. };
  12.  
  13. vertex trie[10000000];
  14. vertex p;
  15. int sz = 0;
  16. int d[9];
  17.  
  18. void add (int x) {
  19.      int m = 0;
  20.      while (x > 0) {
  21.            d[m++] = x % 10;
  22.            x /= 10;
  23.      }
  24.      while (m < 9) d[m++] = 0;
  25.      int v = 0;
  26.      for (int i = m - 1; i >= 0; --i) {
  27.          if (trie[v].next[d[i]] == -1) {
  28.                                 ++sz;
  29.                                 trie[sz - 1].leaf = 0;
  30.                                 for (int j = 0; j < 10; ++j) trie[sz - 1].next[j] = -1;
  31.                                 trie[v].next[d[i]] = sz - 1;
  32.          }
  33.          v = trie[v].next[d[i]];
  34.      }
  35.      ++trie[v].leaf;
  36. }
  37.  
  38. int dfs (int v, int x) {
  39.     if (trie[v].leaf) cout << x << " ";
  40.     for (int i = 0; i < 10; ++i) if (trie[v].next[i] != -1) dfs (trie[v].next[i], x * 10 + i);
  41. }
  42.  
  43. int main () {
  44.     ios_base :: sync_with_stdio (false);
  45.     for (int i = 0; i < 10; ++i) trie[0].next[i] = -1;
  46.     trie[0].leaf = 0;
  47.     sz = 1;
  48.     int n;
  49.     cin >> n;
  50.     for (int i = 0; i < n; ++i) {
  51.         int a;
  52.         cin >> a;
  53.         add (a);
  54.     }
  55.     dfs (0, 0);
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement