一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 576|回复: 12
收起左侧

[数组] 问一道题的follow up

[复制链接] |试试Instant~ |刷题, 数组
我的人缘0

分享帖子到朋友圈
wst1234 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
最近面试onsite 被 问道了 一道题,

首先原题是这样的, 一个数组,里面只有只有0和1,把0排到前面去,{1,0,1,1,0, 1} ->{0,0,1,1,1}
这道题第一问很简单,
方法1:统计0 的个数
方法2: 双指针法,

方法2的代码:

void sort(int[] A) {
        int left = 0, right = A.length - 1;
        while( left < right) {
                while(left < right && A[left] == 0) {
                        left++;
                }
                while(left < right && A[right] == 1) {
                        right--;
                }
                if(left < right) {
                        int tmp = A[left];
                        A[left] = A[right];
                        A[right] = tmp;
                        left++;
                        right--;
                }
        }
}
               
我当时写了方法二的代码,follow up 是 如果 数组是类似{1,0,1,0,0, X, X, X, X } 这样,X代表其他的未知数(不为0或1), 如何修改代码?
大家来讨论下
       

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:大家有没有推荐的效果非常好的中文网络课堂,交钱的也可以啊
下一篇:【面试新题】绝妙的二分查找题,一定要练习一下
我的人缘0
bobli1993 2019-5-16 11:29:59 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
这个有点像DNF问题啊,参考:https://en.wikipedia.org/wiki/Dutch_national_flag_problem
把所有非0,1的元素当做一种元素,排在末尾就好?
回复

使用道具 举报

我的人缘0
nlx 2019-5-16 11:35:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (72)
 
 
1% (1)    👎
是要求XXX这些字符排在0和1中间?要不要保证XXX本身的次序?
回复

使用道具 举报

我的人缘0
609064231 2019-5-16 12:24:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   70% (119)
 
 
29% (50)    👎
这不就是283吗
回复

使用道具 举报

我的人缘0
渣渣程序员 2019-5-16 13:27:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (163)
 
 
8% (16)    👎
我最近也被问到了。。。当初有点卡壳,太惨了。
最简单的办法就是用两个指针从end开始往前遍历,先把非0的元素都填上。指针1到起点以后,把指针2之前的所有数字都填0。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (44)
 
 
0% (0)    👎
283 从后面开始扫
回复

使用道具 举报

我的人缘0
 楼主| wst1234 2019-5-17 04:04:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎
zoey59 发表于 2019-5-16 15:47
283 从后面开始扫

不是283,我可能没说清楚,  最后输出要是 {0,0,0,,x,x, x,x ,1, 1} 这样的
回复

使用道具 举报

我的人缘0
 楼主| wst1234 2019-5-17 04:04:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎

不是283,我可能没说清楚,  最后输出要是 {0,0,0,,x,x, x,x ,1, 1} 这样的
回复

使用道具 举报

我的人缘0
 楼主| wst1234 2019-5-17 04:05:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎
nlx 发表于 2019-5-16 11:35
是要求XXX这些字符排在0和1中间?要不要保证XXX本身的次序?

对的, xxxx在中间,顺序没关系
回复

使用道具 举报

我的人缘0
 楼主| wst1234 2019-5-17 04:08:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (18)
 
 
5% (1)    👎
渣渣程序员 发表于 2019-5-16 13:27
我最近也被问到了。。。当初有点卡壳,太惨了。
最简单的办法就是用两个指针从end开始往前遍历,先把非0的 ...

我当时第一反应也是283 move zeros那道题, 但不是那样的, 最后输出要是 {0,0,0,x,x, x,x ,1, 1} 这样的,
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-23 16:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表