数组类常见面试大题

1，数组排序

http://www.cnblogs.com/bobodeboke/p/3416716.html

2，数组查找

http://www.cnblogs.com/bobodeboke/p/3430211.html

3，输入：一个长度为n的整数数组input
输出：一个长度为n的整数数组result,满足result[i]=input数组中除了input[i]之外所有数值的乘机
要求：时间复杂度为O(n)
思路：使用辅助数组，right[]和left[];left[i]记录input[i]之前所有元素的成绩，right[i]记录input[i]之后所有元素的乘积

4，一个数组，里面的数据没有任何限制，要求求出这样的数a[i],其左边的数都小于等于它，右边的数都大于等于它

借助于辅助数组rightMin[i];记录原始数组array[i]右侧（包括它自己）的最小值。

之后开始从头遍历整个数组，如果当前的最大值刚好等于rightMin[i];那么这个最大值一定满足条件

其实，本质的思想很简单，就是左边的最大值和右边的最小值重合了

5，数组中出现次数超过一般的元素

这三个问题的答案，相见代码部分和p22的讲解

#include<iostream>
using namespace std;
//数组相关的面试题

//题目一
//输入：一个长度为n的整数数组input
//输出：一个长度为n的整数数组result,满足result[i]=input数组中除了input[i]之外所有数值的乘机
//要求：时间复杂度为O(n)
//思路：使用辅助数组，right[]和left[];left[i]记录input[i]之前所有元素的成绩，right[i]记录input[i]之后所有元素的乘积

int* cal(int* input,int n){
        int* result=new int[n];
        int* left=new int[n];
        int* right=new int[n];
        left[0]=1;
        right[n-1]=1;
        int i=0;
        for(i=1;i<n;i++){
                left[i]=left[i-1]*input[i-1];
        }
        for(i=n-2;i>=0;i--){
                right[i]=right[i+1]*input[i+1];
        }
        for(i=0;i<n;i++){
                result[i]=left[i]*right[i];

        }
        delete[] left;
        delete[] right;
        return result;
}

//题目2：一个数组，里面的数据没有任何限制，要求求出这样的数a[i],其左边的数都小于等于它，右边的数都大于等于它
void smallLarge(int* array, int n){
        int* small=new int[n];
        int i;
        small[n-1]=array[n-1];
        for(i=n-2;i>=0;i--){
                if(small[i+1]>array[i]){
                        small[i]=array[i];
                }else{
                        small[i]=small[i+1];
                }
        }
        for(i=0;i<n;i++){
        cout<<small[i]<<" ";

        }
        cout<<endl;
        int max=0;
        for(i=0;i<=n-1;i++){
                if(max<array[i]){
                        max=array[i];
                }
                if(max==small[i]){
                        cout<<array[i]<<endl;
                }
        }
        delete[] small;
}

//题目三
//数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字

int findNumMoreThanHalf(int* array ,int n){
        int currentNum=array[0];
        int curretnTime=1;
        for(int i=1;i<n;i++){
                if(currentTime==0){
                        currentNum=array[i];
                        currentTime=1;
                }
                if(array[i]!=currentNum){
                        currentTime--;
                }else{
                        currentTime++;
                }
        }
        return currentNum;

}
int main(){
        int input[]={7,10,2,6,19,22,32};
        smallLarge(input,7);
        return 0;
}