Yahoo两次电面

axlwu 发表于 2016-11-20 15:50
我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇 ...

这个算法好像 是nlogn的

axlwu 发表于 2016-11-20 15:50
我去google了一下 发现好像大家提的算法很少有one pass + O(1) space的 有一个是说 从array的最左边开始 遇 ...

按照题目的要求的话，用冒泡排序（类似）就好了，先从头往右边找到第一段连续负数区间，然后让负数一个一个通过交换沉下去，直到碰到下一个负数，接着继续同样的操作在下一段更大的负数区间

求问楼主后来有消息了吗？

johnjavabean 发表于 2016-11-18 13:42
记录个从后面开始的index，遇到负数和index的那个数交换，index-1，最后reverse从index到末尾的所有数

这是错的吧，正数没法保证顺序，1，2，-4，4，5，-3
结果是1，2，5，4，-4，-5

我觉得要求既然是inorder inplace onepass，那么复杂度肯定不是O(n)，而且题目也没要求复杂度O(n)。代码贴上了，没有完整的test，但是至少能pass楼主给的input   public class ArraySplitBySign {     public static void main(String[] args) {         int[] arr = new int[]{3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};         int[] arr1 = new int[]{-3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};         System.out.println(Arrays.toString(arr1));         Solve(arr1);         System.out.println(Arrays.toString(arr1));     }      public static void Solve(int[] nums) {         int i = -1;         int j = 0;         int len = nums.length;         while (j < len) {             while (j < len && nums[j] > 0) {                 j++;             }             if (i == -1) i = j;             while (j < len && nums[j] < 0) {                 j++;             }             int end = j - 1;             while (j < len && nums[j] > 0) {                 j++;             }             if (i != -1) {                 int times = j - end - 1;                 for (int k = end; k >= i; k--) {                     for (int t = 0; t < times; t++) {                         swap(nums, k + t, k + t + 1);                     }                 }             }             i = j - end + i - 1;             System.out.println(i);         }     }      private static void swap(int[] nums, int i, int j) {         int t = nums[i];         nums[i] = nums[j];         nums[j] = t;     } }  我的指针j就是唯一的一次pass， i 实际上是没有iterate的，只用来记录而已。

补充内容 (2017-1-22 06:10):
格式不对，见下一楼

格式不对 重发一下
我觉得要求既然是inorder inplace onepass，那么复杂度肯定不是O(n)，而且题目也没要求复杂度O(n)。代码贴上了，没有完整的test，但是至少能pass楼主给的input


public class ArraySplitBySign {
    public static void main(String[] args) {
        int[] arr = new int[]{3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};
        int[] arr1 = new int[]{-3, -10, -2, -5, 10, 4, 5, -1, 10, 2, -4};
        System.out.println(Arrays.toString(arr1));
        Solve(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    public static void Solve(int[] nums) {
        int i = -1;
        int j = 0;
        int len = nums.length;
        while (j < len) {
            while (j < len && nums[j] > 0) {
                j++;
            }
            if (i == -1) i = j;
            while (j < len && nums[j] < 0) {
                j++;
            }
            int end = j - 1;
            while (j < len && nums[j] > 0) {
                j++;
            }
            if (i != -1) {
                int times = j - end - 1;
                for (int k = end; k >= i; k--) {
                    for (int t = 0; t < times; t++) {
                        swap(nums, k + t, k + t + 1);
                    }
                }
            }
            i = j - end + i - 1;
            System.out.println(i);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

我的指针j就是唯一的一次pass， i 实际上是没有iterate的，只用来记录而已。