剑指offer数组3

面试题11：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

考察对二分查找的理解

1. 定义两个指针。第一个 index1 指向第一个元素，第二个 index2 指向最后一个元素。

2. 数组的中间元素 indexMid。如果该中间元素位于前面的递增子数组，那么它大于等于第一个指针指向的元素（最小的元素应该在后面）。index1 = indexMid

如果中间元素位于后面的递增子数组，那么它小于等于第二个指针指向的元素（最小的元素应该在前面）index2 = indexMid

3. 最终两个指针会相邻，第二个指针指向的刚好是最小的元素

特殊情况：

数组{1，0，1，1，1}和数组{1， 1， 1， 0， 1}都看以看成递增排序数组{0， 1， 1， 1， 1}的旋转

当两个指针指向的数字及它们中间的数字三者相同，我们无法判断中间元素位于前面的子数组还是后面的子数组。不得不采用顺序查找的方法。

#include <exception>

class Solution {

public:

    int minNumberInRotateArray(vector<int> rotateArray) {

        int size = rotateArray.size();

        if(size == ){

            return ;

        }

        int left = ,right = size - ;

        int mid = ;

        while(rotateArray[left] >= rotateArray[right]){

            if(right - left == ){

                mid = right;

                break;

            }

            mid = left + (right - left) / ;

            // rotateArray[left] rotateArray[right] rotateArray[mid]三者相等

            // 无法确定中间元素是属于前面还是后面的递增子数组

            // 只能顺序查找

            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){

                return MinOrder(rotateArray,left,right);

            }

            // 中间元素位于前面的递增子数组

            // 此时最小元素位于中间元素的后面

            if(rotateArray[mid] >= rotateArray[left]){

                left = mid;

            }

            // 中间元素位于后面的递增子数组

            // 此时最小元素位于中间元素的前面

            else{

                right = mid;

            }

        }

        return rotateArray[mid];

    }

private:

    // 顺序寻找最小值

    int MinOrder(vector<int> &num,int left,int right){

        int result = num[left];

        for(int i = left + ;i < right;++i){

            if(num[i] < result){

                result = num[i];

            }//if

        }//for

        return result;

    }

};

面试题56：数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O（n），空间复杂度为O（1）

假设输入数组{2， 4， 3， 6， 3， 2， 5， 5}。当我们依次对数组中的每个数字进行异或运算之后，得到的结果是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1，将该数组分为两个子数组。第一个子数组{2， 3， 6， 3， 2}中所有数字的倒数第二位都是1，而第二个子数组{4， 5， 5}中所有数字的倒数第二位是0。接下来对每个子数组求异或，第一个子数组的结果是6，第二个子数组的结果是4

class Solution {

public:

    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        int length = data.size();

        if(length < )

            return;

        int resultExclusiveOR = ;

        for(int i = ; i < length; ++i)

        {

            // 所有元素相异或，得到结果。本例为0010

            resultExclusiveOR ^= data[i];

        }

        // indexOf1 为倒数第二位

        unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

        *num1 = *num2 = ;

        for(int j = ; j < length; ++j)

        {

            if(IsBit1(data[j], indexOf1))

                *num1 ^= data[j];

            else

                *num2 ^= data[j];

        }

    }

    // 找到最右边是1的位

    unsigned int FindFirstBitIs1(int num)

    {

        int indexBit = ;

        while(((num & ) == ) && (indexBit <  * sizeof(int)))

        {

            num = num >> ;

            ++indexBit;

        }

        return indexBit;

    }

    // IsBit1 是判断在num的二进制表示中从右边数起的indexBit位是不是1

    bool IsBit1(int num, unsigned int indexBit)

    {

        num = num >> indexBit;

        return (num & );

    }

};

面试题57：和为s的数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

class Solution {

public:

    vector<int> FindNumbersWithSum(vector<int> array,int sum) {

        // 返回的结果是个数组

        vector<int> result;

        int length = array.size();

        if(length <= )

            return result;

        int head = ;

        int behind = length - ;

        while(head < behind)

        {

            int curSum = array[head] + array[behind];

            if(curSum > sum)

            {

                --behind;

            }

            else if(curSum < sum)

            {

                ++head;

            }

            else

            {

                result.push_back(array[head]);

                result.push_back(array[behind]);

                break;

            }

        }

        return result;

    }

};

面试题57（二）：和为s的连续正数序列

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如：输入15，由于1+2+3+4+5=7+8=15，所以打印出3个连续序列1~5、4~6和7~8

class Solution {

public:

    vector<vector<int> > FindContinuousSequence(int sum) {

        vector<vector<int> > result;

        if(sum < )

            return result;

        int small = ;

        int big = ;

        int middle = ( + sum) / ;

        while(small < middle)

        {

            int curSum = (small + big) * (big - small + ) / ;

            if(curSum < sum)

                ++big;

            if(curSum == sum)

            {

                vector<int> res;

                for(int i = small; i <= big; ++i)

                {

                    res.push_back(i);

                }

                result.push_back(res);

                ++small;

            }

            if(curSum > sum)

            {

                ++small;

            }

        }

        return result;

    }

};

巴特西

剑指offer数组3

面试题11：旋转数组的最小数字

面试题56：数组中只出现一次的数字

面试题57：和为s的数字

面试题57（二）：和为s的连续正数序列

最新文章

热门文章