2

对于前段时间的编程课，我们被赋予了一个相对简单的任务，其本质可以归结为：

存储n 个字符串的数组（不是列表），其中n始终 <= m，允许添加新字符串并删除旧字符串。（在本例中，m为 50）

后来和我的朋友讨论这个问题时，我们意识到我们三个人都以不同的方式解决了这个问题。我的问题（出于好​​奇）是我们中的哪一个有最好的答案（所有事情都是平等的）以及为什么。

朋友 A去实现本质上是一个 ArrayList；创建一个具有不同大小的新数组，并使用for循环将原始数组中的所有元素放入新数组中（加上或减去他正在添加/删除的那个）。

朋友 B简单地创建了一个长度为m的数组，通过将元素的值设置为 null 来删除元素（例如array[13] = null），并通过从索引 0 向前擦洗直到找到一个空点来添加元素（这是一个for循环）。

Friend C [Me]还创建了一个长度为m的数组，但在删除字符串时将每个后续值向前移动（即通过for循环将其索引减 1），因此n -1 始终是最后一个值的索引（当n > 0），并且n也是添加新值的索引（消除for添加字符串的循环）。

这是一个相当基础的课程，只要我们做到了，他们就不关心我们是怎么做到的，但我们很好奇。

编辑：我刚刚意识到我遗漏了一些可能很重要的东西。问题指定按值（例如）而不是索引来删除字符串removeString("someString")，这也使得查找值（及其索引）成为一项要求。

4

2 回答 2

1

对我来说，你的版本是最有效的。就像你用System.arraycopy. 原因是 A 对于要添加的每个数组都有 for 循环。B 有两个 for 循环，而你只有一个。

我用你的版本创建了一个示例程序，System.arraycopy我认为这是最有效的方法。

import java.util.Arrays;

public class Sample {

private int currentIndex = 0;
private String[] strings = null;

public Sample(int length) {
    strings = new String[length];
}

public Sample(String[] strs) {
    if(strs == null)
        throw new NullPointerException();
    strings = strs;
}

public boolean add(String str) {
    if (currentIndex == strings.length)
        return false;
    strings[currentIndex++] = str;
    return true;

}

public boolean remove(int index) {
    if (index >= strings.length)
        return false;
    System.arraycopy(strings, index + 1, strings, index, (strings.length
            - index - 1));
    strings[--currentIndex] = null;
    return true;
}

public boolean remove(String value) {
    if (value == null || value.isEmpty()) {
        return false;// we are saved since value is null or empty;)
    }
    for (int count = 0; count < strings.length; count++) {
        if (value.equals(strings[count])) {
            remove(count);
            break;
        }
    }
    return true;
}

/**
 * @param args
 */
public static void main(String[] args) {
    Sample sample = new Sample(5);
    sample.add("a");
    sample.add("b");
    sample.add("c");
    sample.add("d");
    sample.add("e");
    sample.remove("a");

    System.out.println(Arrays.toString(sample.strings));

}

}
于 2012-09-30T06:34:57.377 回答
0

可能没有正确的答案，因为您创建的数组最终会为系统实现。所以这取决于系统要求。但一般考虑效率：

  • 朋友A的解决方案，对我来说似乎很讨厌。创建一个新数组来添加/删除一个元素会浪费内存和 CPU 周期。而且我相信这不是 ArrayList 在 Java 中的实现方式。

  • 朋友 B 的解决方案与朋友 C 的解决方案具有相同的最坏情况时间复杂度，但它可能表现得更好。由于字符串的顺序并不重要，这看起来是最好的。

  • 朋友 C 的解决方案，实际上也很有效。至于添加一个元素，你已经有了索引 ien 因此它应该也能很好地执行。

然而，正如我之前所说，它实际上取决于一个正在实施的系统。但总结一下，我应该说 A < B = C。

迪格维杰

于 2012-09-30T05:50:29.097 回答