如何在10亿数中找出前1000大/小的数？

墨蓝 2022-01-23 01:51 193阅读 0赞

### 一、内存空间足够大 ###

#### 分治法 ####

随机选一个数flag，然后对整个数组进行分割，会得到两部分，前一部分的数都大于flag，后一部分的数都小于flag。

示例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]

如果说前一部分总数大于1000个，那就继续在前一部分进行分割。如果前一部分的数小于1000个，那就在后一部分再进行分割，寻找剩下的数。利用分治法，对左边或者右边进行循环分割，直到找够Top 1000。

**时间复杂度** ：O(N)

**计算过程** ：

我们在进行第一次分割的时候需要花费N，第二次分割的时候，数据量减半了，所以只要花费N/2，同理第三次的时候只要花费N/4，以此类推。而N+N/2+N/4+…取最高指数项，去掉系数，所以这个方法的渐进时间只有O(N)

### 二、内存空间有限 ###

#### 分布式分治法 ####

利用分布式的思想，将数据切分，然后在多台机器上分别计算Top N，然后将这些数汇总再计算Top N。

示例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70 1]

#### 建堆法 ####

> PS：如果是求max Top N，那么在内存中维护一个小顶堆；如果是求min Top N，那么在内存中维护一个大顶堆。这里以max Top N示例。

**原理** ：

小顶堆的堆顶元素是整个堆中最小的，后续数据如果比堆顶还小，那么由于堆中本来就有N个数据，那么自然就不符合条件，可以丢弃了；如果后续数据比堆顶大，那么就说明这个数可能在Top N中，起码当前堆顶元素肯定就不在Top N中了，所以用这个数替换掉当前堆顶，由于这个数不一定是整个堆中最小的，所以还要调整堆，使堆继续保持堆的特性，以便继续判断后面的数据。这个过程遍历完了数据以后，堆中的元素就是要找的Top N了。

**具体做法** ：

先读取前N个数，在内存中创建一个小顶堆。

然后从第N+1个数开始，依次读取后面的数和堆顶数据进行比较，如果堆顶数，那么直接丢弃，否则用这个数替换掉当前的堆顶，然后调整堆，使之保持堆的特性。循环这个过程，遍历完后续数时，此时堆中的数就是max Top N。

**示例** ：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70 2]

**时间复杂度** ：O(N·logN)

**计算过程** ：

建堆的时间复杂度：O(N)

调整堆的时间复杂度：O(N · logN)

所以，总时间复杂度是：O(N·logN)

**示例代码** ：

//
    //@author 分时天月 on 2019/6/1
    //
    
    #include <iostream>
    #include <vector>
    using namespace std;
    
    class TopN{ 
    public:
    	void FindTopN(size_t n, vector<int>& data){ 
    		//用前n个数建一个小顶堆
    		BuildHeap(n, data);
    		//用第n个值后面的数据调整堆
    		for (size_t i = n; i != data.size(); ++i){ 
    			adjust(i, n, data);
    		}
    	}
    	void PrintN(vector<int>& data){ 
    		for (size_t i = 0; i != data.size(); ++i){ 
    			cout << data[i] << " ";
    		}
    		cout << endl;
    	}
    private:
    	size_t parent(size_t n){ 
    		return (n - 1) >> 1;
    	}
    	size_t left_child(size_t n){ 
    		return (n << 1) + 1;
    	}
    	size_t right_child(size_t n){ 
    		return (n << 1) + 2;
    	}
    	void swap(int& a, int& b){ 
    		a ^= b;
    		b ^= a;
    		a ^= b;
    	}
    	//创建一个小顶堆
    	void BuildHeap(size_t n, vector<int>& data){ 
    		for (size_t i = 1; i != n; ++i){ 
    			size_t index = i;
    			//调整堆，保证小顶堆的特性(父节点比左右孩子节点都小)
    			while (index != 0 && data[parent(index)] > data[index]){ 
    				swap(data[index], data[parent(index)]);
    	            //重新设置当前节点的父节点为当前节点,继续向上重复这个过程
    				index = parent(index); 
    			}
    		}
    	}
    	void adjust(size_t i, size_t n, vector<int>& data){ 
    		if (data[i] <= data[0]) return;
    		//置换堆顶
    		swap(data[i], data[0]);
    		//调整堆
    		size_t index = 0;
    		while ((left_child(index) < n && data[index] > data[left_child(index)]) ||
    			   (right_child(index) < n && data[index] > data[right_child(index)])){ 
    			if (right_child(index) < n && data[right_child(index)] < data[left_child(index)]){ 
    				swap(data[index], data[right_child(index)]);
    				index = right_child(index);
    			}
    			else{ 
    				swap(data[index], data[left_child(index)]);
    				index = left_child(index);
    			}
    		}
    	}
    };
    
    //测试
    int main(){ 
    	TopN t;
    	vector<int> v{  56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34 };
    	cout << "原数组：";
    	t.PrintN(v);
    	t.FindTopN(5, v);
    	cout << "调整后数组：";
    	t.PrintN(v);
    	cout << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]: /images/20220123/3244767a11f044c1a9f02ddc78d7de90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70 1]: /images/20220123/dea0640a9efa4dacae0be4dbdbc35d95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70 2]: /images/20220123/c14c0246f8b443d4b5c4dc956192e0ba.png