Advertisement
Guest User

Zadanko algorytmiczne SM

a guest
Apr 30th, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.95 KB | None | 0 0
  1. private List<Integer> getAExcludingPrimeOccurencesInB(ArrayList<Integer> arrayA, ArrayList<Integer> arrayB) {
  2.         List<Integer> result = new ArrayList<>();
  3.  
  4.         //get max value from array B
  5.         int maxValue = Integer.MIN_VALUE;
  6.         for(Integer val: arrayB) {
  7.             if(val > maxValue) {
  8.                 maxValue = val;
  9.             }
  10.         }
  11.  
  12.         //count occurences in array B
  13.         int [] occurences = new int[maxValue + 1];
  14.  
  15.         for(Integer val: arrayB) {
  16.             occurences[val] += 1;
  17.         }
  18.  
  19.         // 0 - not checked, 1 - prime, -1 - not prime
  20.         int [] primeChecked = new int[maxValue + 1];
  21.  
  22.         //fill result array
  23.         Iterator<Integer> iteratorA = arrayA.iterator();
  24.         int value, occurence;
  25.         while(iteratorA.hasNext()) {
  26.             value = iteratorA.next();
  27.             if(primeChecked[value] == 0) {          //check if number of occurences is prime
  28.                 occurence = occurences[value];
  29.                 if(occurence <= 1) {                //not prime
  30.                     primeChecked[value] = -1;
  31.                     result.add(value);
  32.                 } else if(occurence == 2) {         //prime
  33.                     primeChecked[value] = 1;
  34.                 } else if(occurence % 2 == 0) {     //not prime
  35.                     primeChecked[value] = -1;
  36.                     result.add(value);
  37.                 } else {
  38.                     primeChecked[value] = 1;
  39.                     for(int i = 3; i*i < occurence; i += 2) {
  40.                         if (occurence % i == 0) {    //not prime
  41.                             primeChecked[value] = -1;
  42.                             result.add(value);
  43.                             break;
  44.                         }
  45.                     }
  46.                 }
  47.             } else if(primeChecked[value] == -1) {  //number of occurences is not prime
  48.                 result.add(value);
  49.             }
  50.         }
  51.         return result;
  52.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement