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

Question

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

具有函数third_greatest（），它接受一个字符串数组并返回第三大单词。因此，例如：如果数组是[“你好”、“世界”、“之前”、“中午”]，则输出应该是“世界”，因为“之前”是六个字母长，“你好”和“世界”都是5个，但输出应该是“世界”，因为它显示为数组中最后一个五个字母的单词。如果数组是[“你好”、“世界”、“之后”、“中午”]，则输出应该是“之后”，因为前三个单词都是五个字母长，所以返回最后一个。数组至少有三个字符串，每个字符串只包含字母。

我提出的解决方案使用HashMap以字典方式存储字符串。Hashmap将以整数和ArrayList的形式存储数据、长度和具有该长度的单词。一旦代码完成对字符串数组的迭代并将各个字符串放入各自的组中，我就从Hashmap中提取数组中找到的所有键（长度），并按升序对它们进行排序。之后，Hashmap的ArrayList中的所有值都将传输到另一个ArrayList。最后，它将新ArrayList的第三个字符串返回给函数调用方。

谢谢

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

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

这是一种解决方案，因为排序步骤是O（NlogN）。

这是一个O（N）的解决方案。

• 从输入数组中提取前3个字符串并对其排序。这个由3个元素组成的数组将代表到目前为止输入数组的第三、第二和最大元素

最后，您将执行测试，最多执行3或4个元素数组的排序。总体复杂度为O（N）。

可以对排序步骤进行微观优化，以避免循环和不必要的数组创建和复制。

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

Answer 2

按流的长度降序排序，并跳过前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);
    }
}

或

只需按降序排列数组并返回第三个元素

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

return words[2];