Java: 如何统计ArrayList中不重复(只出现一次)的字符串?
Java: how to count non-repeated (occurring only once) Strings in ArrayList?
我正在尝试查找在 ArrayList
中只出现一次的字符串数。
我实现了多少(最好具有最佳时间复杂度)?
下面是我的方法:
public static int countNonRepeats(WordStream words) {
ArrayList<String> list = new ArrayList<String>();
for (String i : words) {
list.add(i);
}
Collections.sort(list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i).equals(list.get(i - 1))) {
list.remove(list.get(i));
list.remove(list.get(i - 1));
}
}
System.out.println(list);
return list.size();
}
为什么不删除 list.get(i)
和 list.get(i-1)
处的字符串?
这里有一个简单的建议:
- 首先,按字母数字顺序对数组进行排序
- 循环遍历,
if( !list.get(i).equals(list.get(i+1)) ) → unique
- 如果您发现重复项,请递增
i
直到找到不同的字符串
这将有排序算法的复杂性,因为步骤 2+3 应该是 O(n)
是否有使用 ArrayList
的特定需求?您可以使用 HashSet
.
轻松完成
这是代码片段:
public static void main (String[] args) {
String[] words = {"foo","bar","foo","fo","of","bar","of","ba","of","ab"};
Set<String> set = new HashSet<>();
Set<String> common = new HashSet<>();
for (String i : words) {
if(!set.add(i)) {
common.add(i);
}
}
System.out.println(set.size() - common.size());
}
输出:
3
修改后的代码如下:
public static int countNonRepeats(WordStream words) {
Set<String> set = new HashSet<>();
Set<String> common = new HashSet<>();
for (String i : words) {
if(!set.add(i)) {
common.add(i);
}
}
return (set.size() - common.size());
}
你可以使用 hashmap 来实现 this.With 这种方法我们可以计算所有单词的出现次数,
如果我们只对独特的单词感兴趣,那么访问 count = 1 的元素。
HashMap<String,Integer>
- 键表示数组列表中的字符串,整数表示出现次数。
ArrayList<String> list = new ArrayList<String>();
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
for (int i = 0; i < list.size(); i++) {
String key = list.get(i);
if (hashMap.get(key) != null) {
int value = hashMap.get(key);
value++;
hashMap.put(key, value);
} else {
hashMap.put(key, 1);
}
}
int uniqueCount = 0;
Iterator it = hashMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry) it.next();
if ((int) pair.getValue() == 1)
uniqueCount++;
}
System.out.println(uniqueCount);
不需要排序。
更好的方法是使用两个 HashSet,一个用于维护重复词,一个用于维护非重复词。由于HashSet内部使用了HashMap,理想情况下contains、get、put操作的复杂度为o(1)。因此,这种方法的总体复杂度为 o(n)。
public static int countNonRepeats(List<String> words) {
Set<String> nonRepeating = new HashSet<String>();
Set<String> repeating = new HashSet<String>();
for (String i : words) {
if(!repeating.contains(i)) {
if(nonRepeating.contains(i)){
repeating.add(i);
nonRepeating.remove(i);
}else {
nonRepeating.add(i);
}
}
}
System.out.println(nonRepeating.size());
return nonRepeating.size();
}
我正在尝试查找在 ArrayList
中只出现一次的字符串数。
我实现了多少(最好具有最佳时间复杂度)?
下面是我的方法:
public static int countNonRepeats(WordStream words) {
ArrayList<String> list = new ArrayList<String>();
for (String i : words) {
list.add(i);
}
Collections.sort(list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i).equals(list.get(i - 1))) {
list.remove(list.get(i));
list.remove(list.get(i - 1));
}
}
System.out.println(list);
return list.size();
}
为什么不删除 list.get(i)
和 list.get(i-1)
处的字符串?
这里有一个简单的建议:
- 首先,按字母数字顺序对数组进行排序
- 循环遍历,
if( !list.get(i).equals(list.get(i+1)) ) → unique
- 如果您发现重复项,请递增
i
直到找到不同的字符串
这将有排序算法的复杂性,因为步骤 2+3 应该是 O(n)
是否有使用 ArrayList
的特定需求?您可以使用 HashSet
.
这是代码片段:
public static void main (String[] args) {
String[] words = {"foo","bar","foo","fo","of","bar","of","ba","of","ab"};
Set<String> set = new HashSet<>();
Set<String> common = new HashSet<>();
for (String i : words) {
if(!set.add(i)) {
common.add(i);
}
}
System.out.println(set.size() - common.size());
}
输出:
3
修改后的代码如下:
public static int countNonRepeats(WordStream words) {
Set<String> set = new HashSet<>();
Set<String> common = new HashSet<>();
for (String i : words) {
if(!set.add(i)) {
common.add(i);
}
}
return (set.size() - common.size());
}
你可以使用 hashmap 来实现 this.With 这种方法我们可以计算所有单词的出现次数,
如果我们只对独特的单词感兴趣,那么访问 count = 1 的元素。
HashMap<String,Integer>
- 键表示数组列表中的字符串,整数表示出现次数。
ArrayList<String> list = new ArrayList<String>();
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
for (int i = 0; i < list.size(); i++) {
String key = list.get(i);
if (hashMap.get(key) != null) {
int value = hashMap.get(key);
value++;
hashMap.put(key, value);
} else {
hashMap.put(key, 1);
}
}
int uniqueCount = 0;
Iterator it = hashMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry) it.next();
if ((int) pair.getValue() == 1)
uniqueCount++;
}
System.out.println(uniqueCount);
不需要排序。 更好的方法是使用两个 HashSet,一个用于维护重复词,一个用于维护非重复词。由于HashSet内部使用了HashMap,理想情况下contains、get、put操作的复杂度为o(1)。因此,这种方法的总体复杂度为 o(n)。
public static int countNonRepeats(List<String> words) {
Set<String> nonRepeating = new HashSet<String>();
Set<String> repeating = new HashSet<String>();
for (String i : words) {
if(!repeating.contains(i)) {
if(nonRepeating.contains(i)){
repeating.add(i);
nonRepeating.remove(i);
}else {
nonRepeating.add(i);
}
}
}
System.out.println(nonRepeating.size());
return nonRepeating.size();
}