2012-06-20 2 views
1

J'essaie de résoudre le défi médian de interviewstreet. J'ai vu une question similaire posté ici: interviewstreet median challenge mais je veux savoir ce qui ne va pas avec mon approche. J'utilise la recherche binaire et une ArrayList triée pour trouver la médiane à chaque point. Seuls les 1er, 3ème et 10ème tests réussissent, tout le reste échoue avec Mauvaise Réponse. Question: http://pastebin.com/1QhbiB2U Voici le code:Défi médiatique des entrevues: Java

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    Scanner in = new Scanner(System.in); 
    long N = in.nextLong(); 
    List<Long> list = new ArrayList<Long>(); 
    for(int i=0; i<N; i++){ 
     String op = in.next(); 
     long number = in.nextLong(); 
     performOperation(op, number, list); 
    } 
} 

private static void performOperation(String op, long number, List<Long> list) { 
    int index = Collections.binarySearch(list, number); 
    if(op.equalsIgnoreCase("r")){ 
     if(index < 0){ 
      System.out.println("Wrong!");//Doesn't exist 
      return; 
     }else{ 
      list.remove(index);//Remove any one occurence 
     } 
    }else{ 
     if(index < 0){ 
      list.add(-index-1, number);//Add in sorted list 
     }else{ 
      list.add(index, number);//Add where the same number exists, should still be sorted. 
     } 
    } 

    if(list.size() == 0){ 
     System.out.println("Wrong!"); 
    }else if(list.size()%2 == 0){ 
     double median = (list.get(list.size()/2) + list.get(list.size()/2 - 1))/2.0; 
     if(median == Math.ceil(median)) 
      System.out.println((long)median); 
     else 
      System.out.println(median); 
    }else{ 
     System.out.println(list.get((list.size()-1)/2)); 
    } 
} 
+0

Quelle est la question à laquelle votre code tente de répondre? – Thomash

+0

C'est là dans le lien que j'ai mentionné. Quoi qu'il en soit, je l'ai copié ici: http://pastebin.com/1QhbiB2U – cryptonite

+0

Votre lien sur pastebin ne fonctionne pas. – Maddy

Répondre

3

Je pense que problème est avec la sortie du double dans le programme ci-joint. J'ai vérifié que le programme de la question pour l'entrée:

2 
a 1 
a 1000000000 

donne:

1 
5.000000005E8 

Un tel changement fonctionne pour le cas ci-dessus (bien que ce n'est pas très agréable):

long median = (list.get(list.size()/2) + list.get(list.size()/2 - 1)); // median is multiplied by 2 
    if(1==(median&1)) 
     //odd 
    System.out.println(""+(median/2)+".5"); 
else 
    System.out.println(median/2); 

et notez que ArrayList.add avec l'index est O (n).

+0

Eh bien, c'était embarrassant :). Merci de l'avoir signalé, c'était le problème. – cryptonite