从 Java 中的字符串数组中查找第三大字符串

Question

我的一个朋友问我关于他们的讲师作为练习给他们的编码挑战。我有一个解决方案可以解决它。但我认为解决方案对于一个简单的分类问题来说太长了。所以想请教一下有没有更直接的方法来解决这个问题

具有函数 third_greatest()，该函数接受一个字符串数组，return 是第三大单词。因此，例如：如果数组是 ["hello", "world", "before", "noon"]，输出应该是“world”，因为“before”是六个字母长，而“hello”和“world” " 都是 5，但输出应该是 "world"，因为它出现在阵列。如果数组是 ["hello", "world", "after", "noon"]，输出应该是 "after" 因为前三个单词都是五个字母长，所以 return 最后一个。该数组将至少包含三个字符串，每个字符串仅包含字母。

我想出的解决方案是使用HashMap 以字典方式存储字符串。 Hashmap 将以 Integer 和 ArrayList 的形式存储数据，长度和具有该长度的单词。一旦代码完成迭代字符串数组并将相应的字符串放入它们单独的组中，然后我从 Hashmap 中提取数组中找到的所有键（长度），并按升序对它们进行排序。之后Hashmap的ArrayList中的所有值都会被转移到另一个ArrayList中。最后，return将新 ArrayList 的第三个 String 传给函数调用者。

谢谢。

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;


class Main {
    public static void main (String args[]) {
        String test[] = {"hello", "world", "before", "noon"};
        System.out.println(third_greatest(test));
    }

    public static String third_greatest(String words[]) {
        HashMap<Integer, ArrayList<String>> words_length = new HashMap<Integer, ArrayList<String>>();
        for (String word : words) {
            int length = word.length();
            if (words_length.containsKey(length)) {
                words_length.get(length).add(word);
            } else {
                ArrayList<String> temp = new ArrayList<String>();
                temp.add(word);
                words_length.put(length, temp);
            }
        }
        Object keys[] = words_length.keySet().toArray();
        Integer sorted[] = new Integer[words_length.size()];
        for (int x = 0; x < keys.length; x++) {
            sorted[x] = (Integer)keys[x];
        }
        Arrays.sort(sorted);
        ArrayList<String> results = new ArrayList<String>();
        for (int x = sorted.length - 1; x >= 0; x--) {
            ArrayList<String> temp = words_length.get(sorted[x]);
            for (String word : temp) {
                results.add(word);
            }
        }
        return results.get(2);
    }
}

Answer 1

按流的长度降序对流进行排序并跳过前 2 个元素。需要 java 11

import java.util.*;

class ThirdLongest
{
    public static void main(String[] args) {
        String[] words={"Word","Longer Word","Longest Word Here"};
        
        String word=Arrays.stream(words)
            .sorted((s1,s2)->Integer.compare(s2.length(),s1.length()))
            .skip(2)
            .findFirst()
            .get();
                
       System.out.println(word);
    }
}

或

只需按降序对数组进行排序，return第 3 个元素

Arrays.sort(words,(s1,s2)->Integer.compare(s2.length(),s1.length()));

return words[2];

Answer 2

正如其他人所指出的，简单的解决方案是根据字符串大小（或任何排序标准）对数组进行排序。然后从排序列表中取出倒数第三个元素。

这是一个 O(NlogN) 的解决方案，因为排序步骤是 O(NlogN)。

这是一个O(N)解决方案。

从输入数组中取出前 3 个字符串并对它们进行排序。这个 3 数组将代表输入数组的第三个、第二个和最大的元素到目前为止。
遍历其余数组元素：
- 如果元素小于当前第三大元素忽略它
- 否则：
  - 将当前元素添加到3的数组中
  - 排序
  - 删除第一个（最小）元素。

最后，您将执行 O(N) 次测试和至多 O(N) 种 3 或 4 元素数组。对于 O(N).

的整体复杂性

micro-optimizing 排序步骤可以避免循环和不必要的数组创建和复制。

注意：如果输入列表总是很小，那么这个（更复杂的）解决方案就不值得付出努力。当缩放变量具有较小的值时，具有更好的算法复杂性并不能保证更好的性能。

从 Java 中的字符串数组中查找第三大字符串

Finding the third largest string from an array of strings in Java

java

arrays

algorithm

arraylist