I wanted help regarding Java program to find out second shortest string from a list of strings.
开发者_StackOverflowCan I please have suggestions about:
- How to start?
- How to use iterator for this?
- What is efficient way of solving this?
You could use Collections.sort with a comparator that compares two strings based on their length. Afterwards, you can take the second element from the sorted collection.
Note: This is not the most efficient approach, but as long as performance is not an issue, I'd suggest to use the simplest thing that could possibly work.
In case strings of equal length should be taken into account (i.e. the second shortest string out of ["a", "b", "cc"]
would be "cc"
), then you could create a hashmap with the length of the strings as a key and a list of strings of that length as their value and taking the second smallest key's value.
Maintain two variables the length of the shortest and the length of the second shortest string. So let them be first
and second
.
first = len(list[0]), second = len(list[0]);
for every other element cur do:
curLen = len(cur);
if (curLen < first):
second = first;
first = curLen;
else
if (curLen < second && curLen > first):
second = cur;
I assume here that you want the second shortest string to have a different length that the shortest string. If you don't want that remove the && curLen > first
.
You can maintain along another two variables for the actual strings or just keep what are their indexes in the list.
Iterate through list and maintain top two length along with index.
For Example :
ab
abc
abcd
a
abcdef
xyz
iterate through and have top length = 6 and position = 4, also second top length = 4, position = 3
I would say:
String[] loveLetters = {"Roses are red, ...", "I<3U", "I don't have time for a poem."};
String[] shortest = {"",""}; //The shortest and the second shortest.
for (int i=0;i<loveLetters.length;i++) {
if (shortests[0].equals("") || loveLetters[i].length() < shortest[0].length()) {
shortest[1] = shortest[0];
shortest[0] = loveLetters[i];
}
else if (shortest[1].equals("") || loveLetters[i].length() < shortest[1].length()) {
shortest[1] = loveLetters[i];
}
}
System.out.println("What? The second shortest love letter you wrote me was: " + shortest[1] + "!!?! You should write more!");
Rough idea:
- Use a for loop to iterate through the collection
- Use two local variables (
String actualShortestString, actualSecondShortestString
, defined outside of the loop) to store the shortest and second shortest string Math.min(actualString.length(), actualShortestString.length())
will help.- the second shortest String is the previous shortest String
Note - you're asked to implement a Select algorithm to find the kth smallest element. Wikipedia has a some background and algorithms for that task.
精彩评论