几种有关排序的常见面试问题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54694992

1、荷兰国旗问题

题目描述:现有n个红白蓝三种不同颜色的小球,乱序排列在一起,请通过两两交换任意两个球,使得从左至右,依次是一些红球、一些白球、一些蓝球。


分析与解法:

初看此题,我们貌似除了暴力解决并无好的办法,但联想到我们所熟知的快速排序算法呢?

我们知道,快速排序依托于一个partition分治过程,在每一趟排序的过程中,选取的主元都会把整个数组排列成一大一小的部分,那我们是否可以借鉴partition过程设定三个指针完成重新排列,使得所有球排列成三个不同颜色的球呢?


解法:

通过前面的分析得知,这个问题类似快排中partition过程,只是需要用到三个指针:一个前指针begin,一个中指针current,一个后指针end,current指针遍历整个数组序列,当

1.current指针所指元素为0时,与begin指针所指的元素交换,而后current++,begin++ ; 2.current指针所指元素为1时,不做任何交换(即球不动),而后current++ ; 3.current指针所指元素为2时,与end指针所指的元素交换,而后,current指针不动,end– 。

为什么上述第3点中,current指针所指元素为2时,与end指针所指元素交换之后,current指针不能动呢?因为第三步中current指针所指元素与end指针所指元素交换之前,如果end指针之前指的元素是0,那么与current指针所指元素交换之后,current指针此刻所指的元素是0,此时,current指针能动么?不能动,因为如上述第1点所述,如果current指针所指的元素是0,还得与begin指针所指的元素交换。

ok,说这么多,你可能不甚明了,直接引用下gnuhpc的图,就一目了然了:

参考代码如下:

#include<iostream>
#include<vector>
using namespace std;
class ThreeColor {
public:
    vector<int> sortThreeColor(vector<int> &A, int n)
    {
        int f,r,i,temp;
        for(i=f=0,r=n-1;i<=r;i++)
        {
            if(A[i]==0)
            {
                temp=A[f];
                A[f]=A[i];
                A[i]=temp;
                f++;
            }
            if(A[i]==2)
            {
                temp=A[r];
                A[r]=A[i];
                A[i]=temp;
                r--;
                i--;
            }
        }
        return A;
    }
};
int main()
{
    int a[6]={1,2,0,2};
    vector<int> b(a,a+4);
    ThreeColor c;
    c.sortThreeColor(b,4);
    for(int i=0;i<4;i++)
        cout<<b[i]<<" ";
    cout<<endl;
    return 0;
}

2、求需要排序的最短子数组长度

题目描述: 假设数组为a b c d e f g h i j k l m n,

如果abc是有序的,mn是有序的,至于中间的defghijkl是无序的,我们可以得知,如果是正常升序序列,左边的一定是小于右边的任意数值,右边的一定大于左边的任意数值。


思路:

1、我们从后往前遍历,如果某个元素大于右边最小的元素,就标记,一直遍历到最左边; 2、从前往后遍历,如果某个元素小于左边的最大的元素,则标记,一直遍历到最右边。


参考代码:

#include<iostream>
#include<vector>
using namespace std;
class Subsequence {
public:
    int shortestSubsequence(vector<int> A, int n) 
    {
        int max=A[0],min=A[n-1],i,rd1,rd2;
        for(i=1,rd1=0;i<n;i++)
        {
            if(A[i]>=max)
                max=A[i];
            else
                rd1=i;
        }
        for(i=n-2,rd2=n-1;i>=0;i--)
        {
            if(A[i]<=min)
                min=A[i];
            else
                rd2=i;
        }
        if(!rd1)
            return 0;
        else
            return rd1-rd2+1;
    }
};
int main()
{
    int a[6]={1,4,6,5,9,10};
    vector<int> b(a,a+6);
    Subsequence c;
    int d=c.shortestSubsequence(b,6);
    cout<<d<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python小白到大牛

安利一波Python编程中非常实用的那些黑魔法

编者按:Python是机器学习的主流语言,没有之一。今年5月,它首次在PYPL排行榜上超越JAVA,成为全球第一大编程语言。而一个月后,Stack Overfl...

14120
来自专栏Golang语言社区

第四节 Go语言数据类型

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

8120
来自专栏落影的专栏

程序员进阶之算法练习(三十四)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

14730
来自专栏阿凯的Excel

Python读书笔记19(函数与返回值)

为什么计算机与程序可以简化我们的工作量,因为我们只需要了解输入输出即可,不需要关心中间的计算过程。 那我们今天就聊一下如何使用函数输出返回值。 我们设想有一个函...

30460
来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

33020
来自专栏林德熙的博客

不使用数据结构反转栈

昨天有人问我一道题,我有一个栈,我不使用其他数据结构,不使用另一个栈,把这个栈里所有数据反转。

8010
来自专栏我杨某人的青春满是悔恨

“身首异处”的序列(Swift)

声明:文章开头部分内容翻译自objc的一篇博客。当然,我并没有逐行翻译原文,只是说个大致意思,顺带阐述一些自己的理解和扩展思考,还有我自己的代码。

15220
来自专栏老马说编程

计算机程序的思维逻辑 (3) - 基本运算

运算 上节我们介绍了给数据赋值,有了初始值之后,可以对数据进行运算。计算机之所以称为"计算"机,是因为发明它的主要目的就是运算。运算有不同的类型,不同的数据类型...

20290
来自专栏CDA数据分析师

Python迭代和迭代器详解

一个对象,物理或者虚拟存储的序列。list,tuple,strins,dicttionary,set以及生成器对象都是可迭代的,整型数是不可迭代的。如果你不确定...

21990
来自专栏IT杂记

求一个数组中子数组的最大和算法(Java实现)

    前几天在微信订阅号“待字闺中”中看到的一篇文章《小技巧求一个数组中子数组的最大和》,提供下Java的实现,并且在对题目做下小修改,本来打算直接在微信里直...

35880

扫码关注云+社区

领取腾讯云代金券