• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

一道有关数组正赋值排序的面试题

互联网 diligentman 2周前 (11-20) 10次浏览

前言
上周星期天,我跟一个前一段时间在深圳找工作的学长聊天,他告诉 我他找了一份5位数薪资的工作,当时我也很高兴,然后我接着问了他遇到了哪些面试题,然后他就跟我分享了一道题,题目是这样的:
给定一个整型数组,其中的数值有正有负(我们暂时认为0也算是正数部分),现在请调整位置,把所有负值调到数组的左边,把所有正直调到数组右边。
思路
用一个指针i从前往后找第一个正数,用一个指针j从后往前找第一个负数,找到以后并且i<j,那么就将他们位置互换。这样,就完成了排序,代码如下:

package interview;

/**
 * @author xing xing
 */
public class ArraySort {
    public static void main(String[] args) {
        //定义一个数组
        int [] array = {1,-2,-4,5,9,-3,-8,6};
        arraySort(array);
        print(array);

    }

    public static void arraySort(int[] array) {
        int j = array.length-1;
        int i = 0;
        //定义变量尽量在外面定义,避免重复创建变量浪费空间
        int temp;
        while (i < j) {
            //从前面开始找,找到第一个正数
            while (array[i] < 0) {
                i++;
        }
            //从后面开始找,找到第一个负数
            while (array[j] >= 0) {
                j--;
            }

            //如果这时候i < j ,就将他们交换位置
            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
            //交换完位置以后,两个指针往后移动寻找下一个
            i++;
            j--;


        }
    }

    //打印数组
    public static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

时间复杂度和空间复杂度都很可观,前者为O(n),后者为O(1),这样就大功告成了。


喜欢 (0)