查找有限空間陣列中不同值的數量

Question

給定一個非常大的陣列，分配在HDD = {1,1,5,7,8,1,6,10,20,1}上我們需要找出存在多少不同的值。所提到的陣列的解決方案是7,7個不同的總數{1,5,6,7,6,10,20}。沒有必要保存號碼。

給出了一些提示，我需要在HDD和RAM上工作。但是，HDD明顯大於RAM。所以如果所有值都不同，就不能使用散列表和鏈表。從我的理解，我需要分配K常量固定大小的數組（每個m個元素）。在那之後，我需要填充所有k個數組，將它們中的一個排序。然後比較它們並計算不同的部分並再次填充它們，直到完成硬盤上分配的所有值爲止。我的問題是最後一部分，一旦數組排序後，我需要做什麼？

編輯：rutime例如，HDD可以含有10^10個記錄，RAM可以僅保持10^5， 和K = 10，M = 10，對於處理的每個陣列，有必要以讀取下一個M值到該特定數組。

應該只有一個計數器，說明不同的數值。最大的數字可能是N

謝謝

Answer 1

這是我的解決方案。我定義了2個向量，第一個向量表示Hdd數據，另一個向量表示Hdd向量內的偏移量。

#include <iostream> 
    #include <fstream> 
    #include <vector> 
    #include <algorithm> 
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <iterator> 
    #include <direct.h> 

    #define FILE_NAME "\\data.txt" 
    #define ROWS  10 
    #define MAX_LINE 100 
    #define ARRSIZE(arr) sizeof(arr)/sizeof(arr[0]) 

    class CPair 
    { 
    public: 
     CPair(__int64 nOffset) : m_llOffset(nOffset), m_llCurOffset(nOffset), m_bChecked(0) 
     { } 

     __int64 m_llOffset; 
     __int64 m_llCurOffset; 
     bool m_bChecked; 
    }; 

    std::vector<long>  vecHDD; 
    std::vector<CPair> vecOffsets; 

    long RetrieveValueFromHDD(__int64& i64Offset) 
    { 
     return vecHDD[(long)i64Offset]; 
    } 

    void FindDistinct() 
    { 
     // calculate how many fragments within the HDD we've got 
     long nFragments = (vecHDD.size()/ROWS); 
     long nCount  = 0; 

     while(nFragments > 0) 
     { 
      long nMinimum = INT_MAX; 
      for(int i = 0; i < (int)vecOffsets.size(); i++) 
      { // find the minimum number 
       if((false == vecOffsets[i].m_bChecked) && (RetrieveValueFromHDD(vecOffsets[i].m_llCurOffset) < nMinimum)) 
        nMinimum = vecHDD[(int)vecOffsets[i].m_llCurOffset]; 
      } 

      // start changing indices for values equivalent to nMinimum 
      for(int i = 0; i < (int)vecOffsets.size(); i++) 
      { 
       bool bKeepChanging = true; 
       for(int j = 0; j < ROWS && (true == bKeepChanging) && ((vecOffsets[i].m_llCurOffset - vecOffsets[i].m_llOffset) < ROWS); j++) 
       { 
        if(RetrieveValueFromHDD(vecOffsets[i].m_llCurOffset) == nMinimum) 
         vecOffsets[i].m_llCurOffset++; 
        else // terminate correct fragment 
         bKeepChanging = false; 
       } 

       if ((vecOffsets[i].m_llCurOffset - vecOffsets[i].m_llOffset) >= ROWS && (false == vecOffsets[i].m_bChecked)) 
       { 
        vecOffsets[i].m_bChecked = true; 
        nFragments--; 
       } 
      } 

      std::cout << "distinct number:" << nMinimum << '\n'; 
      nCount++; 
     } 

     std::cout << "total distinctive numbers: " << nCount; 
    } 

    void main() 
    { 
     FILE*  pf; 
     std::string str; 
     long  nCount   = 0; 
     long  arr[ROWS]  = { 0 }; 
     __int64  i64Offset  = 0; 
     char  pDirectoryPath[256 * 2]; 

     // get current location 
     _getcwd(pDirectoryPath, ARRSIZE(pDirectoryPath)); 
     strcat_s(pDirectoryPath, FILE_NAME); 
     fopen_s(&pf, pDirectoryPath, "r"); 
     if (pf == NULL) 
      return; 

     std::vector<CPair>  vecPos; 
     char     pLine[MAX_LINE]; 
     while (0 != fgets(pLine, MAX_LINE, pf)) 
     { 
      arr[nCount] = atoi(pLine); 
      nCount++; 
      if (nCount == ROWS) 
      { 
       // create the offset array, save the start of each fragment 
       vecOffsets.push_back(CPair(i64Offset)); 
       std::vector<long> vec(arr, arr + ARRSIZE(arr)); 
       std::sort(vec.begin(), vec.end()); 

       // continue creating the HDD array, it will hold sorted fragments. 
       vecHDD.insert(vecHDD.end(), vec.begin(), vec.end()); 
       i64Offset += nCount; 
       nCount  = 0; 
      } 
     } 

     FindDistinct(); 
     fclose(pf); 
    }