一道算法，没想明白，帮忙看下

Question

一个不定长数组 下标0 值为 1 下标 2 和 3 值为null，下标 4 值为 5

现在 需要 将null值替换最近的不为null的值
比如
{1,2, null, null, 5, 6, null};

替换为 {1,2, 2, 5, 5, 6, 6};

我使用的最暴力的遍历循环做的，但这样不是最优的
看上去应该是用二分查找来，但没想明白改怎么来？
帮忙指点下

Answer 1

public class LatestInteger {
    public static void main(String[] args) {
        Integer[] source = {1, 2, null, null, 5, 6, null};
        Integer[] left = new Integer[source.length];
        Integer[] right = new Integer[source.length];
        processLeft(source, left);
        processRight(source, right);

        Arrays.stream(left).forEach(item -> System.out.print(item + " "));

        System.out.println("-------------------");
        Arrays.stream(right).forEach(item -> System.out.print(item + " "));

       // System.exit(0);
        for (int i = 0; i < source.length; i++) {
            if (source[i] == null) {
                int leftDistance = (left[i] == -1 ? Integer.MAX_VALUE : (i - left[i]));
                int rightDistance = (right[i] == -1 ? Integer.MAX_VALUE : (right[i] - i));
                source[i] = (leftDistance < rightDistance ? source[left[i]] : source[right[i]]);
            }
        }
        System.out.println("-------------------");
        Arrays.stream(source).forEach(item -> System.out.print(item + " "));
    }

    private static void processLeft(Integer[] source, Integer[] left) {
        left[0] = (source[0] == null ? -1 : 0);
        for (int i = 1; i < source.length; i++) {
            left[i] = (source[i] == null ? left[i - 1] : i);
        }
    }

    private static void processRight(Integer[] source, Integer[] right) {
        int start = source.length - 1;
        right[start] = (source[start] == null ? -1 : 0);
        for (int i = start - 1; i >= 0; i--) {
            right[i] = (source[i] == null ? right[i + 1] : i);
        }
    }
}

Answer 2

艹，看错了，看成了 {1,2, 2, 2, 5, 6, 6}了。。。如果照题主的意思，是生成快照同步替换，那null中间的null确实处理不了

从题主的示例{1,2, null, null, 5, 6, null} 转化为 {1,2, 2, 5, 5, 6, 6}可以看出来：

1. 替换的顺序是从左往右
2. 替换时优先使用左边的值

那么可以推断出：

1. 如果某个null左边没有实数的话，应当是使用右边的值
2. 那么如果右边第一位没有，应该循序找下一位

Answer 3

//大概思路. 从中间劈开,前边一段,后边一段,一起算.不是更快吗

for(int i = 1,int y = arr.length/2; i<arr.length/2 | y<arr.length; i++,y++){
    if(arr[i] == null && arr[i] |= null 
        arr[i] = arr[i];
    }
}

Answer 4

有点斐波那契的意思，可以试试这个思路

Answer 5

感觉题目不够完整啊。简单理解为不存在连续三个的null。那就可以用栈吧

数字栈和null栈

读到数字，如果数字栈为空且null栈不为空可以填写一个null值，如果null栈也为空就压到数字栈

    如果数字栈不为空，出栈元素在压栈

读到null，如果数字栈不为空就填写一个null值

    如果数字栈为空就压null栈
    

描述的很简陋，而且只在1.没有连续三个null的情况下2.开头不是null且结尾不是连续两个null

Answer 6

顶3楼的问题：连续3个null，中间的怎么搞？