java - 如何优化字符串数组的搜索？

Question

我有数组的字符串数组。

List<String[]> mainList = new ArrayList<String[]>();

String[] row1 = {"foo", "bar", "moo"}
String[] row2 = {"cocoa", "zoo", "milk", "coffee"}

mainList.add(row1);
mainList.add(row2);

假设我想找到一个元素“milk”。

我可以用 N^2 来做。

for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        String item = mainList.get(i)[x];

        if(item.equals("milk")) {
            return true; //found milk
        }
    }
}

我试图通过将所有元素作为 Map 键来使其更快。

//put all elements to map key
Map m = new HashMap<String, String>();
for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        m.put(mainList.get(i)[x], "whatever");
    }
}

//now iterate and see if key "milk" is found
if(m.contains("milk")) { return true; }

但我认为这仍然是 N^2(即 for 循环内部的 for 循环，因为添加到 mainList 的行数，如 row3['item1', 'item2', 'item3']，迭代递增 N ^2)

在没有 N^2 的情况下如何优化它？

Answer 1

这两种算法都不是 N^2，因为您只访问元素一次。但是，第一种算法每次查找的时间复杂度为 O(N)，而第二种算法填充 map 的时间复杂度为 O(N)，后续每次查找的时间复杂度为 O(1)。