Mx_zH
HongShield
2020-12-02 22:13
采纳率: 100%
浏览 3

如何将c++ 优先队列求中位数代码修改为模板类?

#include <stdio.h>
#include <queue>
class MedianFinder {
public:
        MedianFinder() {
        }
        void addNum(int num) {
        if (big_queue.empty()){
	big_queue.push(num);
	return;
	}
        if (big_queue.size() == small_queue.size()){
                if (num < big_queue.top()){
	        big_queue.push(num);
	        }
	else{
        small_queue.push(num);
        }
        }
        else if(big_queue.size() > small_queue.size()){
        	if (num > big_queue.top()){
	        	small_queue.push(num);
	        }
	        else{
        		small_queue.push(big_queue.top());
        		big_queue.pop();
        		big_queue.push(num);
        	}
        }
        else if(big_queue.size() < small_queue.size()){
        	if (num < small_queue.top()){
	                big_queue.push(num);
	        }
	        else{
        	        big_queue.push(small_queue.top());
        	        small_queue.pop();
        	        small_queue.push(num);
        	}
                }
        }
        double findMedian(){
    	if (big_queue.size() == small_queue.size()){
        	return (big_queue.top() + small_queue.top()) / 2;
        }
        else if (big_queue.size() > small_queue.size()){
        	return big_queue.top();
        }
        return small_queue.top();
    }
private:
	std::priority_queue<double> big_queue;
	std::priority_queue<double, std::vector<double>,
					std::greater<double>> small_queue;
};
int main(){
	MedianFinder M;
	int test[] = {6, 10, 1, 7, 99, 4, 33};
	for (int i = 0; i < 7; i++){
		M.addNum(test[i]);
		printf("%lf\n", M.findMedian());
	}
	return 0;
}
  • 点赞
  • 收藏

1条回答 默认 最新

  • i_actor
    i_actor 2020-12-03 15:17
    已采纳
    #include<iostream>
    #include<queue>
    
    template <typename T>
    class MedianFinder {
    private:
    	std::priority_queue<T> big_queue;
    	std::priority_queue<T, std::vector<T>,
    		std::greater<T>> small_queue;
    public:
    	MedianFinder(){}
    	template <typename U>
    	void addNum(U& num) {
    		if (big_queue.empty()) {
    			big_queue.push(num);
    			return;
    		}
    		if (big_queue.size() == small_queue.size()) {
    			if (num < big_queue.top())
    				big_queue.push(num);
    			else small_queue.push(num);
    		}
    		else if (big_queue.size() > small_queue.size()) {
    			if (num > big_queue.top())
    				small_queue.push(num);
    			else {
    				small_queue.push(big_queue.top());
    				big_queue.pop();
    				big_queue.push(num);
    			}
    		}
    		else if (big_queue.size() < small_queue.size()) {
    			if (num < small_queue.top())
    				big_queue.push(num);
    			else {
    				big_queue.push(small_queue.top());
    				small_queue.pop();
    				small_queue.push(num);
    			}
    		}
    	}
    	T  findMedian() {
    		if (big_queue.size() == small_queue.size()) return (big_queue.top() + small_queue.top()) / 2;
    		else if (big_queue.size() > small_queue.size()) return big_queue.top();
    		else return small_queue.top();
    	}
    };
    
    int main() {
    	MedianFinder<double> M;
    	int test[] = { 6, 10, 1, 7, 99, 4, 33 };
    	for (auto i = 0; i < 7; i++) {
    		M.addNum(test[i]);
    		printf("%lf\n", M.findMedian());
    	}
    	return 0;
    }

    不知道对不对,我也是正在学习。

    点赞 评论

相关推荐