3

好的，我有一个带有一些值的随机数组：

Integer[] array = {null,null,5,111,21,null,22,null,null,null,98,25,47,null,1,23,null}

我想用null最接近的两个现有数组值的平均值替换所有值。例如：前两个null值需要替换为数字5（{null,null,5,...变成{5,5,5,...）。

下一个例子：{...,22,null,null,null,98,...}应该变成：{...,22,60,60,60,98,...}; 所有三个null值都将替换为22和98( (22+98)/2) 的平均值。

最后一个例子：{...,23,null}应该变成{...,23,23}; null被替换为，23因为它是数组的最后一个元素。

有谁知道如何为这个问题编写算法？

4

4 回答 4

3

假设这是在ArrayList<Integer>：

//iterate over all values
for (int i=0; i<array.size(); i++) {
    //get the value at the current position
    Integer value= array.get(i);

    //if the value is null...
    if (value == null) {

        //find out the closes left and right values
        Integer leftValue= goLeft(array, i);
        Integer rightValue= goRight(array, i);

        //if both are integer values, find middle
        if (leftValue != null && rightValue != null) {
            array.add(i, (leftValue + rightValue)/2);

        //if left one is integer, and the other one is null? end of the array
        } else if (leftValue != null && rightValue == null) {
            array.add(i, leftValue);

        //if the right one is integer, and the left one is null? begin of the array
        } else if (leftValue == null && rightValue != null) {
            array.add(i, rightValue);

        //well, if everything is null, just add zeros
        } else {
            array.add(i, 0);
        }
    }
}

剩下的就是实施

  • goLeft(ArrayList<Integer> array, int index)和
  • goRight(ArrayList<Integer> array, int index).

我认为他们从上下文中非常直接，只需查看他们的名字。

于 2013-06-12T14:15:43.040 回答
0
  1. 确定所有空序列（存储每个序列的开始和结束索引）
  2. 确定每个序列的边界元素并计算平均值（确保正确处理数组的开始和结束的额外情况）
  3. 用计算值替换空值
于 2013-06-12T14:10:24.520 回答
0

这是我的看法：

public static void fill(Integer[] newarr, Integer[] arr, int index) {
    if (arr[index] != null) {
        newarr[index] = arr[index];
        return;
    }

    Integer a = null, b = null;

    int i = index;
    while (i < arr.length - 1 && (a = arr[++i]) == null);

    i = index;
    while (i > 1 && (b = arr[--i]) == null);

    newarr[index] = (a == null) ? b : (b == null) ? a : (a + b) / 2;
}

然后：

Integer[] arr = { null, null, 5, 111, 21, null, 22, null, null, null,
        98, 25, 47, null, 1, 23, null };

Integer[] newarr = new Integer[arr.length];

for (int i = 0; i < arr.length; i++)
    fill(newarr, arr, i);

System.out.println(Arrays.toString(newarr));

[5, 5, 5, 111, 21, 21, 22, 60, 60, 60, 98, 25, 47, 24, 1, 23, 23]
于 2013-06-12T14:29:55.863 回答
-1

一种不同的可能，更简单但可能效率较低的解决方案：

  1. 为每个空值检查左右值 a。如果它们都是数字，取平均值 b。如果一个为空且一个为数字，则将中间值设置为该值，将另一个留空
  2. 重复直到没有空值

它是如何工作的？

{null,null,5,111,21,null,22,null,null,null,98,25,47,null,1,23,null}
{null,5   ,5,111,21,21,  22,  22,null,98  ,98,25,47,24  ,1,23,23  }
{5   ,5   ,5,111,21,21,  22,  22,60  ,98  ,98,25,47,24  ,1,23,23  }

这些值的平均值相同，算法更简单。

优点

  • 无需任何修改即可处理开始/结束空值
  • 需要更少的内存

缺点

  • 做一些不同的事情......！
  • 可能需要多次迭代
  • 在悲观的情况下将需要更多时间
于 2013-06-12T14:16:59.880 回答