一道微软实习生笔试题
2010年11月21日
今儿个第一次参加海笔，以前找实习啥的都是被关在一个小屋子里孤独写代码，一下放到大场合还真不太适应。
闲话少说，直奔主题。
微软今天的考试题很基础，但是涉及的面也很广，对于我这个学电子的人来说，着实有不小的压力，但是对学计算机的人来说，估计就很easy了。
先说编程题，就一道。
在一个有序集合中，找到逆序对的个数, 优化算法，要求O(n*log(n))
O(n^2）的复杂度就不说了。
O(n*log(n)),我想到先快速排序，然后二分查找。将原来的数组排序后放入一个新数组中去，然后用原来数组中的元素做索引，用二分查，然后返回这个元素之前的元素个数，再删除元素，然后累加计数器。后来写到一半的时候，发现了，这不就是二叉搜索树么。。哎，没时间了，就这么写吧。
?
//swapvoid swap(int &a, int &b){int tmp=a;a=b;b=tmp;}//partitionint partition(int *Array,int left,int right,int n){int pivot=Array[left];swap(Array[left],Array[right]);int storeIndex=left;for(int i=left;i<right;++i){if(Array[i]<=pivot){swap(Array[i],Array[storeIndex]);++storeIndex;}}swap(Array[storeIndex],Array[right]);return storeIndex;}// 快速排序void qSort(int *Array, int left, int right, int n){if(right<=left)return;int p=partition(Array,left,right,n);qSort(Array,left,p-1,n);qSort(Array,p+1,right,n);}//删除元素void deleteEle(int index, int *Array, int n){for(int i=index;i<n;++i){Array[i]=Array[i+1];// 后一个覆盖前一个}}// 二分搜索int BinarySearch(int *Array,int low, int high, int n, int x){int mid=0;while(low<=high){mid=(low+high)/2;if(Array[mid]>x){high=mid-1;}else if(Array[mid]<x){low=mid+1;}else{break;}}deleteEle(mid,Array,n);Array[n-1]=2000;return mid;}//O(n*lg(n))int reversePair2(int *array, int n){int *tmpArray=new int[n];for(int i=0;i<n;++i){tmpArray[i]=array[i];}int count=0;qSort(tmpArray,0,n-1,n);for(int i=0;i<n;++i){int index=BinarySearch(tmpArray,0,n-1,n,array[i]);count+=index;}delete [] tmpArray;return count;}? 另外还有选择题，主要涉及图论，字符串，二叉树，前缀运算，位运算，都很基础，但是考的都是细节。
? 先这么多，二叉搜索实现的方法，择日再说
?