題意： 給出2個有序的數組，找出2個數組合并后的中位數，直接合并沒嘗試， 寫了個二叉搜索樹，直接遍歷一遍，找到數就好了， 恩 代碼寫的像屎一樣。
struct node{ int data; node *l,*r; node(){l=r=NULL;} node(int t):data(t){l=r=NULL;}};void insert(node* &root, int val){ if(!root){ root = new node(val); return ; } if(val < root->data){ insert(root->l, val); } else { insert(root->r, val); }}int cnt=0,p1,p2,x,y;double ans;void show(const node* root){ if(!root){ return ; } if(root->l){ show(root->l); } if(cnt==p1)x=root->data; if(cnt==p2)y=root->data;cnt++; if(root->r){ show(root->r); }}class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { node *root=NULL; for(int i=0;i<nums1.size();i++){ insert(root, nums1[i]); } for(int i=0;i<nums2.size();i++){ insert(root, nums2[i]); } cnt=0;int sum = nums1.size()+nums2.size(); p1 = sum/2-1; p2=sum/2; show(root); if(sum&1){ ans = y; } else { ans = (x+y)/2.0; } return ans; }};新聞熱點
疑難解答
