面试某公司碰到的笔试题
- 给定一个由正数,负数和0组成的整数数组,将所有为0的元素,挪到数组末尾。要求时间复杂度O(n)，请设计一个函数,完成此功能。(语言不限)
- 给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)。例如： 给定1233,它的下一个是1323； 给定1323,它的下一个是1332； 给定9876,它的下一个不存在； 请设计一个函数，完成此功能。(语言不限)
第一题，比较简单，相信通过代码可以很快的理解，思路很重要，我的思路是这样的，使用while循环遍历，每次拿到左边为0的数与右边起第一个非0数进行交换，直到左边遍历的位置等于右边遍历的位置了，循环结束。
一、代码展示：
package comployeetest;
public class Test1 {
public static void main(String[] args) {
int[] arr = { , -2, ,,,, , , , , -1, , };
order(arr);
for (int i : arr) {
System.out.print(i + ",");
}
}
public static void order(int[] arr) {
int j = arr.length - ;
int i = ;
int temp;
while (i < j) {
if (arr[j] == ) {
j--;
continue;
}
if (arr[i] == ) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
j--;
}
i++;
}
}
}
二、结果展示：
通过结果可以清楚的看出0都到了右边。
第二题就不是那么简单了，是一道经典的字典序算法题，主要通过三步来实现，在我的代码中，用了三个for循环，每一个for循环都完成了一步。
（1）第一步（体现在第一个for循环）：从右边往左边遍历，找出第一个左边小于右边的，把右边的位置记录了下来。
（2）第二步（体现在第二个for循环）：从右边开始遍历到记录的位置，找出第一个比记录位置左边大的数，让这个数与记录位置左边的数交换。
（3）第三步（体现在第三个for循环）：从记录位置开始到最右边，把所有的数字按照升序排列，按照常规来说的话，如果数字是无序的话，升序或者降序肯定需要双重for循环，时间复杂度不可能是O（n），但是在第一步中遍历的时候，我们已经保证记录点到右边末尾的数是降序的，即有序的，所以只需要一个for循环把左边的与右边的交换位置就行了。
一、代码如下：
public class Test2 {
public static void main(String[] args) {
int a=;
String result=renew(a);
System.out.println(result);
}
public static String renew(int a) {
String aString=String.valueOf(a);
String[] arr=aString.split("");
int[] arr2=new int[arr.length];
for(int i=;i<arr.length;i++) {
arr2[i]=Integer.parseInt(arr[i]);
}
//num为交换的位置
int num=;
for(int i=arr2.length-1;i>;i--) {
if(arr2[i]>arr2[i-1]) {
num=i;
break;
}
if(i==) {
return "它的下一个不存在";
}
}
//交换位置右边的数刚好大于它前一位交换位置
for(int i=arr2.length-1;i>=num;i--) {
if(arr2[num-1]<arr2[i]) {
int temp=arr2[num-1];
arr2[num-1]=arr2[i];
arr2[i]=temp;
break;
}
}
//对num右边的数进行排序,由于第一次找num时就保证了右边比左边小，所以只需要倒序一下就好了
for(int i=num,j=arr2.length-1;i<j;i++,j--) {
int temp=arr2[i];
arr2[i]=arr2[j];
arr2[j]=temp;
}
String result="";
for (int i : arr2) {
result=result+i;
}
return "它的下一个是"+result;
}
}二、总结
以上是我对最近收到的面试题的实现
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
