# 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);
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++) {
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++) {
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