uopspop

Untitled

Sep 28th, 2019
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Arrays;
  2. import java.util.HashSet;
  3. import java.util.Set;
  4.  
  5. public class LongestConsecutiveSubsequence {
  6.  
  7.     ////////// UTIL ///////////
  8.  
  9.     private static void printArray(int[] ary){
  10.         for (int i = 0; i < ary.length; i++) {
  11.             System.out.printf("%4d" , ary[i]);
  12.         }
  13.         System.out.println();
  14.     }
  15.  
  16.  
  17.     public static void main(String[] args) {
  18. //        int[] arr1 = {1, 9, 3, 10, 4, 20, 2};
  19.         int[] arr1 = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42};
  20.  
  21.         // solution 1
  22. //        sortAndFind(arr1);
  23. //        hashBad(arr1);
  24.         hashGood(arr1);
  25.     }
  26.  
  27.     // O(n)
  28.     // 1. 試想著,最後的結果就是一群排列好的數個陣列
  29.     // 我們就是去挑每個陣列的開頭,並往下跑
  30.     // 因此,我們就只會跑過每個陣列元素恰恰好就一次,強。
  31.     // 2. 我們利用了Set.contains() O(1)的高效率
  32.     private static void hashGood(int[] arr) {
  33.  
  34.         Set<Integer> set = new HashSet<>();
  35.         // put ary elements to the set
  36.         for (int i = 0; i < arr.length; i++) {
  37.             set.add(arr[i]);
  38.         }
  39.  
  40.         int longestLengthSoFar = 1;
  41.         for (int i = 0; i < arr.length; i++) {
  42.  
  43.             if (!(set.contains(arr[i] - 1))){
  44.                 // we only process the node that is the first number in a sequence
  45.                 System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose
  46.  
  47.                 int lastNoInSequence = arr[i];
  48.                 while (set.contains(lastNoInSequence + 1)){ // here, it won't be N*N because we will at maxmum check N times for the whole array if we only get into this while loop for those first numbers in the sequence
  49.                     lastNoInSequence++;
  50.                     System.out.print(" -> " + lastNoInSequence);
  51.                 } // end of while
  52.  
  53.                 int lengthEachRun = lastNoInSequence - (arr[i] - 1);
  54.                 System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
  55.                 if (lengthEachRun > longestLengthSoFar) {
  56.                     longestLengthSoFar = lengthEachRun;
  57.                     System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
  58.                 }
  59.             } // end of outer while
  60.  
  61.         }
  62.  
  63.         System.out.println("result: " + longestLengthSoFar);
  64.     }
  65.  
  66.     // O(N*N)
  67.     private static void hashBad(int[] arr) {
  68.  
  69.         Set<Integer> set = new HashSet<>();
  70.         // put ary elements to the set
  71.         for (int i = 0; i < arr.length; i++) {
  72.             set.add(arr[i]);
  73.         }
  74.  
  75.         int longestLengthSoFar = 1;
  76.         for (int i = 0; i < arr.length; i++) {
  77.             System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose
  78.  
  79.             int lastNoInSequence = arr[i];
  80.             while ((set.contains(lastNoInSequence + 1))){
  81.                 lastNoInSequence++;
  82.                 System.out.print(" -> " + lastNoInSequence);
  83.             }
  84.  
  85.             int lengthEachRun = lastNoInSequence - (arr[i] - 1);
  86.             System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
  87.             if (lengthEachRun > longestLengthSoFar) {
  88.                 longestLengthSoFar = lengthEachRun;
  89.                 System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
  90.             }
  91.         }
  92.  
  93.         System.out.println("result: " + longestLengthSoFar);
  94.     }
  95.  
  96.     // O(N*log(N) + N) = O(N*log(N))
  97.     private static void sortAndFind(int[] arr) {
  98.  
  99.         Arrays.sort(arr);
  100.         printArray(arr); // for debug purpose
  101.  
  102.         int longestLengthSoFar = 1;
  103.         int lengthEachRun = 1;
  104.         int prevNo = -1;
  105.         for (int i = 0; i < arr.length; i++) {
  106.  
  107.             if (lengthEachRun == 1) System.out.print("start a new round - starting num: " + arr[i]); // for debug purpose
  108.  
  109.             if (arr[i] == prevNo + 1) {
  110.                 System.out.print(" -> " + arr[i]);
  111.                 lengthEachRun++;
  112.             }else{
  113.                 System.out.print("\r\nend this round - lengthEachRun: " + lengthEachRun + "\r\n"); // for debug purpose
  114.                 if (lengthEachRun > longestLengthSoFar){
  115.                     longestLengthSoFar = lengthEachRun;
  116.                     System.out.println("update the longestLengthSoFar to " + longestLengthSoFar); // for debug purpose
  117.                 }
  118.  
  119.                 // reset
  120.                 lengthEachRun = 1;
  121.  
  122.             }
  123.  
  124.             prevNo = arr[i];
  125.         }
  126.  
  127.         System.out.println("result: " + longestLengthSoFar);
  128.     }
  129. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×