求一高效率算法

Question

将一个元素项目为字符串的List拆分为2个map,map中key为字符串在List中的index，值为List中的字符串项目，1个map保存List中重复的数据，另一个保存非重复的数据。求一超高效率的算法。

Answer 1

先把list里的数据排序,然后判断相临的是否相同,有相同的放到一个map,和前后都不同的放到另外一个.

Answer 2

List list = new ArrayList();
list.add("a");
list.add("b");
list.add("b");
list.add("b");
list.add("c");
list.add("a");
list.add("d");
list.add("a");

HashMap map1 = new HashMap();//重复
HashMap map2 = new HashMap();//非重复
for(int i=0;i<list.size();i++){

if(map2.values().contains(list.get(i))){
map1.put(list.indexOf(list.get(i))+"", list.get(i));
map1.put(i+"", list.get(i));
map2.values().remove(list.get(i));
}else if(map1.values().contains(list.get(i)))
map1.put(i+"", list.get(i));
else
map2.put(i+"", list.get(i));
}

Answer 3

        Map<Integer, String> map1 = new HashMap<Integer, String>(); //存在重复的
        Map<Integer, String> map2 = new HashMap<Integer, String>(); //不存在重复的
        Map<String, Integer> values = new HashMap<String, Integer>();
        for(int i = 0; i < list.size(); i++) {
         String value = list.get(i);
         Integer index = values.put(value, Integer.valueOf(i));
         if(index != null) {
         map2.remove(index);
         map1.put(index, value);
         } else {
         map2.put(Integer.valueOf(i), value);
         }
        }
        System.out.println(map1.values());
        System.out.println(map2.values());

Answer 4

改了一点点
Map<Integer, String> map1 = new HashMap<Integer, String>(); //存在重复的
Map<Integer, String> map2 = new HashMap<Integer, String>(); //不存在重复的
Map<String, Integer> oldValues = new HashMap<String, Integer>();
for(int i = 0; i < list.size(); i++) {
String value = list.get(i);
Integer index = Integer.valueOf(i);
Integer oldIndex = oldValues.put(value, index);
if(oldIndex != null) {
map2.remove(oldIndex);
map1.put(oldIndex, value);
} else {
map2.put(index, value);
}
}
System.out.println(map1.values());
System.out.println(map2.values());

Answer 5

还要再改改，呵呵
Map<Integer, String> map1 = new HashMap<Integer, String>(); //存在重复的
Map<Integer, String> map2 = new HashMap<Integer, String>(); //不存在重复的
Map<String, Integer> oldValues = new HashMap<String, Integer>();
for(int i = 0; i < list.size(); i++) {
    String value = list.get(i);
    Integer index = Integer.valueOf(i);
    Integer oldIndex = oldValues.put(value, index);
    if(oldIndex != null) {
        map2.remove(oldIndex);
        map1.put(oldIndex, value);
        map1.put(index, value);
    } else {
        map2.put(index, value);
    }
}
System.out.println(map1.values());
System.out.println(map2.values());

Answer 6

重复的Value少插了一个的吧，比如3个a只插了2个到map中。

Answer 7

map用List代替了，原因是我不知道在map中怎么根据value去找到对应的key。
如果有写得不好的地方，还请大虾们指正一下，想求一速度最快的算法。                ArrayList<String> ss = new ArrayList<String>();

ss.add("2");
ss.add("2");
ss.add("1");
ss.add("2");
ss.add("1");
ss.add("2");
ss.add("3");
ss.add("2");
ss.add("6");
ss.add("2");
ss.add("7");
ss.add("2");
ss.add("8");
ss.add("2");
ss.add("2");


for (int i = 0; i <9985; i++ ) {
ss.add("5");
}


int size = ss.size();

                //我自己想出来的算法
long beginTime1 = System.currentTimeMillis();
ArrayList<String> repeat1 = new ArrayList<String>();

ArrayList<String> only1 = new ArrayList<String>();

ArrayList<String> clone = new ArrayList<String>(ss);

for (int i = 0; i < size; i++) {
boolean found = false;

String istr = clone.get(i);

if (null == istr) {
continue;
}
for (int j = i + 1; j < size; j++) {
String jstr = clone.get(j);

if (null == jstr) {
continue;
}

if (istr.equals(jstr)) {
found = true;

repeat1.add(jstr);

clone.set(j, null);
}
}

if (found) {
repeat1.add(istr);
clone.set(i, null);
} else {
only1.add(istr);
}
}
long endTime1 = System.currentTimeMillis();
System.err.print("2 loop:");
System.err.println(endTime1 - beginTime1);

//
//
// for (String str : repeat) {
// System.err.println(str);
// }
//
// System.err.println("######");
// for (String str : only) {
// System.err.println(str);
// }

//用3楼的思路作的，稍微修改了下，把漏掉的一条加了进来。
long beginTime = System.currentTimeMillis();
ArrayList<String> repeat = new ArrayList<String>();//repeat
ArrayList<String> only = new ArrayList<String>();

for(int i = 0; i < size; i++) {
repeat.add(null);
only.add(null);
}

        for (int i = 0; i < size; i++) { if (only.contains(ss.get(i))) { repeat.set(i, ss.get(i));
int index = only.indexOf(ss.get(i));
if (only.remove(ss.get(i))) {
repeat.set(index, ss.get(i));
}
} else if (repeat.contains(ss.get(i))) {
repeat.set(i, ss.get(i));
} else { only.set(i, ss.get(i));
} }
        
        long endTime = System.currentTimeMillis();
        System.err.print("1 loop:");
        System.err.println(endTime - beginTime);
// for (String str : repeat) {
// System.err.println(str);
// }
//
// System.err.println("######");
//
// for (String str : only) {
// System.err.println(str);
// }

Answer 8

初学java,我也写了个．．．
---------------------------------------------------------------
结果:
交集: [red, green]
差集: [blue, pink, yellow]
---------------------------------------------------------------
import java.util.*;
public class Sets {
/**交集*/
public static Set<String> intersection(Set<String> setA, Set<String> setB) {
Set<String> setIntersection = new HashSet<String>();
String s = "";
Iterator<String> iterA = setA.iterator();
while (iterA.hasNext()) {
s = iterA.next();
if(setB.contains(s)) {
setIntersection.add(s);
}
}
return setIntersection;
}
/**差集*/
public static Set<String> difference(Set<String> setA, Set<String> setB) {
Set<String> setDifference = new HashSet<String>();
String s = "";
Iterator<String> iterA = setA.iterator();
while (iterA.hasNext()) {
s = iterA.next();
if(!setB.contains(s)) {
setDifference.add(s);
}
}
return setDifference;
}

public static void main(String[] args) {
String[] strA = {"green", "blue", "red", "pink", "yellow"},
 strB = {"red", "green"}; 
Set<String> setA = new HashSet<String>(),
            setB = new HashSet<String>(),
            setC = null;

/**将数组元素舔加到集合*/
for (int i = 0; i < strA.length; i++) {
setA.add(strA[i]);
}
for (int i = 0; i < strB.length; i++) {
setB.add(strB[i]);
}

/**求交集结果*/
setC = intersection(setA, setB);
System.out.println("交集: " + setC);
/**求差集结果*/
setC = difference(setA, setB);
System.out.println("差集: " + setC);

}
}

Answer 9

Java 的格式不熟悉，代码就不写了，提供一个思路
1 HashMap map = new HashMap( list.size() * 2); // 要保证效率的话，必须指定hashmap的size
2.for(int i = 0; i < list.size(); i++) { // counting sort
     map[list[i]]++；
}
3.for (int i = 0; i <map.size(); i++) {
     if (map.at(i) > 1) 
             write to map1
     else
             write to map2
}整体来说，速度应该是Ｏ（ｎ）．不过构造hashmap比较花时间，适用list比较大的时候

Answer 10

List list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("b");
        list.add("b");
        list.add("c");
        list.add("a");
        list.add("d");
        list.add("a");
        String temp = null;
        HashMap map1 = new HashMap();//重复
        HashMap map2 = new HashMap();//非重复
        for(int i=0;i<list.size();i++){
         temp = (String)list.get(i);
            if(list.indexOf(temp)==list.lastIndexOf(temp)){
             map2.put(String.valueOf(i), temp);
            }else{
             map1.put(String.valueOf(i), temp);
            }       
        }

Answer 11

写一段吧,java不好，有错不要鄙视我/*init size of map preventing from auto expand */
Map<Integer, String> map1 = new HashMap<Integer, String>(list.size()); //non repeat
Map<Integer, String> map2 = new HashMap<Integer, String>(list.size()); //repeat/* 
Values store pair of string / string occurrence
size of hashmap must be double of list in order to get optimal performance
*/
Map<String, Integer> Values = new HashMap<String, Integer>(list.size() * 2);/* 
update into hashmap 
each loop would be done in constant time
*/
for(int i = 0; i < list.size(); i++) {
    String value = list.get(i);
    Integer Occured = Values.get(value);
    
    if(Occured == null) {
       Values.put(value,Integer.valueOf(1); 
    } else {
       Values.put(value,Integer.valueOf(Occured+1);
    }
}
/*
write to map
note: it is posible to be O(nlogn), depend on enqueue algorithm of map
*/
for(int i = 0; i < list.size(); i++) {
    String value = list.get(i);
    Integer Occured = Values.get(value);
    
    if(Occured == 1) {
       map1.put(index, value);
    } else {
       map2.put(index, value);
    }
}/*
special note : it based on ChDw's implemmentation with system 
               level optimization
note 1. expected to be faster when list is larger then 1000 only
note 2. code based on C++ philosphy, further optimization can be 
        for JAVA
note 3. for auto expand in map structure, take a look on java spec       */

Answer 12

写一段吧,java不好，有错不要鄙视我/*init size of map preventing from auto expand */
Map<Integer, String> map1 = new HashMap<Integer, String>(list.size()); //non repeat
Map<Integer, String> map2 = new HashMap<Integer, String>(list.size()); //repeat/* 
Values store pair of string / string occurrence
size of hashmap must be double of list in order to get optimal performance
*/
Map<String, Integer> Values = new HashMap<String, Integer>(list.size() * 2);/* 
update into hashmap 
each loop would be done in constant time
*/
for(int i = 0; i < list.size(); i++) {
    String value = list.get(i);
    Integer Occured = Values.get(value);
    
    if(Occured == null) {
       Values.put(value,Integer.valueOf(1); 
    } else {
       Values.put(value,Integer.valueOf(Occured+1);
    }
}
/*
write to map
note: it is posible to be O(nlogn), depend on enqueue algorithm of map
*/
for(int i = 0; i < list.size(); i++) {
    String value = list.get(i);
    Integer Occured = Values.get(value);
    
    if(Occured == 1) {
       map1.put(index, value);
    } else {
       map2.put(index, value);
    }
}/*
special note : it based on ChDw's implemmentation with system 
               level optimization
note 1. expected to be faster when list is larger then 1000 only
note 2. code based on C++ philosphy, further optimization can be 
        for JAVA
note 3. for auto expand in map structure, take a look on java spec       */

Answer 13

用你的作测试时，发现当list很大时，还是没有我的那个快

Answer 14

而且大量相同的key会严重拖慢hashmap的表现

Answer 15

那我觉得用Hash表+桶来实现,可以比较好的解决这个问题:"而且大量相同的key会严重拖慢hashmap的表现"

Answer 16

LZ。不如拿你的测试数据来吧
long   beginTime   =   System.currentTimeMillis(); 
List list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("b");
        list.add("b");
        list.add("c");
        list.add("a");
        list.add("d");
        list.add("a");
        for   (int   i   =   0;   i   <9985;   i++   )   { 
         list.add("5"); 
         } 
        String temp = null;
        HashMap map1 = new HashMap();//重复
        HashMap map2 = new HashMap();//非重复
        Set set=new HashSet();
        
        for(int i=0;i<list.size();i++){
            temp = (String)list.get(i);
            if(set.add(temp)){
                map1.put(String.valueOf(i), temp);
            }else{
                map2.put(String.valueOf(i), temp);
            }           
        }
        long   endTime   =   System.currentTimeMillis(); 
        System.err.println(endTime   -   beginTime);