鍍金池/ 問答/Java/ 一道算法,沒想明白,幫忙看下

一道算法,沒想明白,幫忙看下

一個(gè)不定長(zhǎng)數(shù)組 下標(biāo)0 值為 1 下標(biāo) 2 和 3 值為null,下標(biāo) 4 值為 5

現(xiàn)在 需要 將null值替換最近的不為null的值
比如
{1,2, null, null, 5, 6, null};

替換為 {1,2, 2, 5, 5, 6, 6};

我使用的最暴力的遍歷循環(huán)做的,但這樣不是最優(yōu)的
看上去應(yīng)該是用二分查找來(lái),但沒想明白改怎么來(lái)?
幫忙指點(diǎn)下

回答
編輯回答
嘟尛嘴

//大概思路. 從中間劈開,前邊一段,后邊一段,一起算.不是更快嗎

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];
    }
}
2017年12月30日 12:03
編輯回答
愛是癌

感覺題目不夠完整啊。簡(jiǎn)單理解為不存在連續(xù)三個(gè)的null。那就可以用棧吧

數(shù)字棧和null棧

讀到數(shù)字,如果數(shù)字棧為空且null棧不為空可以填寫一個(gè)null值,如果null棧也為空就壓到數(shù)字棧

    如果數(shù)字棧不為空,出棧元素在壓棧

讀到null,如果數(shù)字棧不為空就填寫一個(gè)null值

    如果數(shù)字棧為空就壓null棧
    

描述的很簡(jiǎn)陋,而且只在1.沒有連續(xù)三個(gè)null的情況下2.開頭不是null且結(jié)尾不是連續(xù)兩個(gè)null

2018年9月5日 11:05
編輯回答
陪我終

有點(diǎn)斐波那契的意思,可以試試這個(gè)思路

2017年10月31日 18:08
編輯回答
空白格

艸,看錯(cuò)了,看成了 {1,2, 2, 2, 5, 6, 6}了。。。如果照題主的意思,是生成快照同步替換,那null中間的null確實(shí)處理不了

從題主的示例{1,2, null, null, 5, 6, null} 轉(zhuǎn)化為 {1,2, 2, 5, 5, 6, 6}可以看出來(lái):

  1. 替換的順序是從左往右
  2. 替換時(shí)優(yōu)先使用左邊的值

那么可以推斷出:

  1. 如果某個(gè)null左邊沒有實(shí)數(shù)的話,應(yīng)當(dāng)是使用右邊的值
  2. 那么如果右邊第一位沒有,應(yīng)該循序找下一位
2017年3月15日 18:18
編輯回答
獨(dú)特范

頂3樓的問題:連續(xù)3個(gè)null,中間的怎么搞?

2017年12月20日 13:29
編輯回答
涼汐
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);
        }
    }
}
2017年12月25日 00:54