面试算法题总结

快速找到数组中出现次数超过一半的数字 O(n)

快排思路： 基于Partition()的算法

出现次数超过一半的数字也就是中位数，第k/2大的数

int Partition(vector<int>& A , int start , int end){//闭区间
	int base = A[start];//base可以随意选择
    int low = start;
    int high = end;
    while(low<high){
         while(A[low]<=base){
             low++;
         }
        while(A[high]>base){
            high--;
        }
         if(low<high){
		        std::swap(A[low],A[high]) ;
    	}
    }
    std::swap(A[high],A[start]);
    return high;//high之前的数都小于A[high],即A[high]是第high大的数
}
int main(){
    int A[]={1,3,4,5,5,5,5,5,0};
    vetcor<int> nums;
    nums.assign(A,A+sizeof(A)/sizeof(int));
    int left = 0, right = nums.size()-1;
    int k = Partition(nums,left,right);
    int rankk=nums.size/2;
    while(k!=rankk){
        if(k<rankk){
            left = k;
            k = Partition(nums,left,right);
        }else if(k>rankk){
            right = k;
            k = Partition(nums,left,right);
        }
    }
    cout<<"the result is " << nums[k];
}

中缀表达式转后缀表达式

这里为了更好地区分操作数和运算符，我们使用string来表示每个操作符