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 回答