排序数组相关面试题总结

  1. 旋转数组中的最小元素如{3,4,5,1,2},就是{1,2,3,4,5}左旋两个得到,因为数组可以分为两个递增的部分,左边大于右边,用二分法的思想,中间元素如5大于2,说明5在左边部分,最小元素在右半部分,缩小区间到{5, 1, 2}之间。时间复杂度为O(logN).

    注:如果左边元素与右边元素中间元素相同,需要另外处理。如{1,1,1,0,1}和{1,0,1,1,1}都是旋转数组,无法用二分法判断。

int  _Min(int *arr, int left, int right)
{
    if (NULL == arr || left < 0 || right  right)
        throw new exception("参数错误");
    for (int i = left+1; i  arr[i])
            arr[left] = arr[i];
    }
    return arr[left];
}

int Min(int *arr, int sz)
{
    if (NULL == arr || sz =  arr[right])
    {
         mid = left + ((right - left) >> 1);
        if (right - left == 1)
        {
            arr[mid] = arr[right];
            break;
        }

        if (arr[left] == arr[right] &&
            arr[left] == arr[mid])
        {
            return _Min(arr, left, right);
        }
        else if (arr[mid] >= arr[right])
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
    return arr[mid];
}

2.数组中出现超过一半的数字

数组中超过一半的数字排序后一定位于数组的中间位置。但是全部排序耗费时间。

快速排序可以将数组分为两部分,左半部分小于等于关键值,右半部份大于等于关键值,当关键值恰好位于中间位置时,它就是要找的元素。

注:这种方法会改变数组的顺序

int partition(int *arr, int left, int right)
{
    int slow = left - 1;
    for (int fast = left; fast < right; ++fast)
    {
        if (arr[fast] < arr[right])
        {
            slow++;
            if (slow != fast)
                swap(arr[slow], arr[fast]);
        }
    }
    ++slow;
    swap(arr[slow], arr[right]);

    return slow;
}

bool invalied = false;

bool check(int *arr, int sz, int ret)
{
    int count = 0;
    for (int i = 0; i  sz)
    {
        invalied = true;
        return ret;
    }
    else return 0;
}

int MoreThanHalf(int *arr, int sz)
{
    if (NULL == arr || sz > 1);
    while (index != mid)
    {
        if (index > mid)
            index = partition(arr, left, index - 1);
        else
            index = partition(arr, index + 1, right);
    }

    int ret =check (arr,sz,arr[mid]);
    return ret;

}

如果不希期忘改变顺序,可以用计数的方法,ret与下一次数相同加一,小于0更新ret。超过一半最后一定会留下。

int MoreThanHalf_2(int *arr, int sz)
{
    invalied = false;
    if (NULL == arr || sz < 1)
        return 0;
    int result = arr[0];
    int times = 1;
    for (int i = 1; i < sz; ++i)
    {
        if (times == 0)
        {
            result = arr[i];
            times = 1;
        }
        else if (arr[i] == result)
            times ++ ;
        else 
            times--;
    }
    result = check(arr, sz, result);
    return result;
}

3.数组最小的K个数

方法与上一题相同,快速排序可以将数据分为两部分,小于关键值,大于关键值得,如果关键值下标恰好是K,前面的K个数就是要找的数。

注:会改变数据的顺序

void SmallKnum(int *arr, int sz, int K)
{
    if (NULL == arr || sz < K)
        return;
    int left = 0;
    int right = sz - 1;
    int index = partition_(arr, left, right);
    while (index != K)
    {
        if (index < K)
        {
            left = index + 1;
            index = partition_(arr, left, right);
        }
        else
        {
            right = index - 1;
            index = partition_(arr, left, right);
        }
    }

    for (int i = 0; i < index; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

用multiset(底层红黑树,可以报存相同的元素)/大堆, 保存K个最小值,有值小于multiset中的最大值时,更新。

这里用multiset实现:

typedef multiset  Set;
typedef multiset::iterator Setit;

void SmallKnum_(int *arr, int sz, int K)
{
    if (NULL == arr || sz < 1 || sz < K)
        return;
    Set myset;
    Setit it = myset.begin();
    for (int i = 0; i < sz; ++i)
    {

        if (myset.size() < K)
        {
            myset.insert(arr[i]);
        }
        else
        {
            Setit it  = myset.begin();
            if (arr[i] < *myset.begin())
            {
                myset.erase(it);
                myset.insert(arr[i]);
            }
        }
    }

    for (it = myset.begin() ; it != myset.end(); ++it)
        cout << *it << " ";
    cout << endl;

}

4.数组中的逆序对

用归并排序,先将数组分到最小,排序合并。

int _InverseMerge(int *arr, int *copy, int left, int right)
{
    if (left == right)
        return 0;
    int mid = (left + ((right - left) >> 1));   
    int leftPairs = _InverseMerge(arr, copy, left, mid);
    int rightPairs = _InverseMerge(arr, copy, mid+1, right);
    int end = right;
    int i = mid;
    int j = right;
    int Pairs = 0;
    while (left <= i && mid + 1  arr[j])
        {
            Pairs += (j - mid);
            copy[right--] = arr[i];
            i--;
        }
        else
        {
            copy[right--] = arr[j];
            j--;
        }
    }
    if (left <= i) 
    {
        copy[right--] = arr[i--];
    }
    if (mid + 1 <= j)  
    {
        copy[right--] = arr[j--];
    }

    for (; left <= end; ++left)
    {
        arr[left] = copy[left];
    }
    return Pairs + leftPairs + rightPairs;
}

int InversePairs(int arr[], int sz)
{
    if (NULL == arr || sz < 2)
        return 0;

    int *copy = new int[sz];
    return _InverseMerge(arr, copy, 0, sz-1);
    delete[]copy;
}

5.数字在排序数组中出现的次数

排序好的数组可以用二分法,因为是重复数字,先找第一次出现的位置,找到K,如果K左边的数字相同,继续往左边找,直到下标为0或者左边元素不相同为止,同方法找到最后一次出现的位置。两个相减就是出现的次数。

int GetFirstK(int *arr, int sz, int K)
{
    if (NULL == arr || sz < 1)
        return -1;
    int left = 0;
    int right = sz - 1;
    while (left > 1);
        if (arr[mid] > K)
        {
            right = mid - 1;
        }
        else if (arr[mid] < K)
        {
            left = mid + 1;
        }
        else
        {
            if (mid == 0)
                return mid;
            else if (arr[mid - 1] != K)
                return mid;
            else
                right = mid - 1;
        }
    }

    return -1;
}

int GetLastK(int *arr, int sz, int K)
{
    if (NULL == arr || sz < 1)
        return -1;
    int left = 0;
    int right = sz - 1;
    while (left > 1);
        if (arr[mid] > K)
        {
            right = mid - 1;
        }
        else if (arr[mid] < K)
        {
            left = mid + 1;
        }
        else
        {
            if (mid == sz-1)
                return mid;
            else if (arr[mid + 1] != K)
                return mid;
            else
                left = mid + 1;
        }
    }

    return -1;
}

int HasMoreK(int *arr, int sz, int K)
{
    int lastK = GetLastK(arr, sz, K);
    int firstK = GetFirstK(arr, sz, K);
    if (lastK == -1 || firstK == -1)
        return 0;
    return lastK - firstK + 1;
}

6.扑克牌是否为顺子,大王可以看做任意牌

把扑克牌用数字替代,A为1,JQK为,11,12,13,大王看作0,先对数据排序,统计0的个数,在统计相差(两张牌之间差几个)的个数,看是否能用0抵消。

int partition_2(int *arr, int left, int right)
{
    int slow = left - 1;
    for (int i = left; i < right; ++i)
    {
        if (arr[i] < arr[right])
        {
            slow++;
            if (slow != i)
                swap(arr[i], arr[slow]);
        }
    }
    ++slow;
    swap(arr[slow], arr[right]);
    return slow;
}

void qSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int index = partition_2(arr, left, right);
        qSort(arr, left, index - 1);
        qSort(arr, index + 1, right);
    }
}

//把大王看作0
bool IsContinue(int *arr, int sz)
{
    if (NULL == arr || sz < 1)
        return false;

    qSort(arr,0,sz-1);
    //0的数目
    int zeronums = 0;
    for (int i = 0; i < sz; ++i)
    {
        if (0 == arr[i])
            zeronums++;
        else
            break;
    }
    //第一个不为0的下标
    int small = zeronums;
    int big = small + 1;

    int difference = 0;
    while (big < sz) 
    {
        //如果相等一定不为顺子
        if (arr[big] == arr[small])
            return false;
        //计算相邻卡片多余的差
        difference += (arr[big] - arr[small] - 1);
        small++;
        big++;
    }
    //多余的差是否能用0填充
    return (difference  <= zeronums );
}

7.n个数,数的范围是0~n-1。求任意一个重复出现的数。

由于数的大小在0~n-1之间,所以可以用arr[n] = n的顺序排序,如{2, 3, 1, 0, 2, 5, 3},从第一个数开始,下标为0,值为2,不匹配,把2交换到下标为2的位置.

{1, 3, 2, 0, 2, 5, 3},不匹配,把1交换到下标为1的位置

{3, 1, 2, 0, 2, 5, 3},不匹配,把3交换到下标为3的位置

{0, 1, 2, 3, 2, 5, 3}匹配,下标为1,2,3也匹配,跳过

下标为4的值是2,交换,发现与下标为2的值相同,则找到相同元素返回。

这种方法每次查找都会把一个元素归位,所以最坏是O(n)。

bool repeatnum(int *arr, int sz)
{
    if (NULL == arr || sz < 2)
        return false;

    for (int i = 0; i < sz;++i)
    {
        while (arr[i] != i)  //不等于下标交换位置
        {
            //待交换位置上的元素与当前元素相同,找到重复元素
            if (arr[i] == arr[arr[i]])  
            {
                cout << arr[i] << endl;
                return true;
            }
            swap(arr[i], arr[arr[i]]); //移动元素位置
        }
    }
    return false;  //没找到重复元素
}
CSDN博客稿源:CSDN博客 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » 排序数组相关面试题总结

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录