|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | 3 | importjava.util.ArrayList; |
4 | | -importjava.util.Collections; |
5 | | -importjava.util.Comparator; |
6 | | -importjava.util.Date; |
7 | 4 | importjava.util.List; |
8 | 5 |
|
9 | 6 | /** |
| 7 | + * 386. Lexicographical Numbers |
| 8 | + * |
10 | 9 | * Given an integer n, return 1 - n in lexicographical order. |
11 | | -
|
12 | | -For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. |
13 | | -
|
14 | | -Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.*/ |
| 10 | + * |
| 11 | + * For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. |
| 12 | + * |
| 13 | + * Please optimize your algorithm to use less time and space. The input size may be as large as |
| 14 | + * 5,000,000. |
| 15 | + */ |
15 | 16 | publicclass_386 { |
16 | | -//Radix sort doesn't apply here! Don't confuse myself! |
17 | | - |
18 | | -//rewrote their solution from Python to Java:https://discuss.leetcode.com/topic/54986/python-memory-limit-exceeded-for-problem-386/17 |
19 | | -publicstaticList<Integer>lexicalOrder(intn) { |
20 | | -List<Integer>result =newArrayList(); |
21 | | -inti =1; |
22 | | -while (true) { |
23 | | -result.add(i); |
24 | | -if (i *10 <=n) { |
25 | | -i *=10; |
26 | | - }else { |
27 | | -while (i %10 ==9 ||i ==n) { |
28 | | -i /=10; |
29 | | - } |
30 | | -if (i ==0) { |
31 | | -returnresult; |
32 | | - } |
33 | | -i++; |
34 | | - } |
35 | | - } |
36 | | - } |
37 | | - |
38 | | -//someone on Discuss hinted that you could use recursion to solve it in Java |
39 | | -//then I wrote the following method, eventually, got all test cases produce the right output, but unfortunately TLE'ed by OJ |
40 | | -publicstaticList<Integer>lexicalOrder_LTE_by_10458(intn) { |
41 | | -List<Integer>result =newArrayList(); |
42 | | -intinsertPosition =0; |
43 | | -returnaddNumbers(result,1,insertPosition,n); |
44 | | - } |
45 | | - |
46 | | -privatestaticList<Integer>addNumbers(List<Integer>result,intinsertNumber,intinsertPosition,intn) { |
47 | | -inti; |
48 | | -for (i =0;i <9;i++) { |
49 | | -if (insertNumber +i >n) { |
50 | | -returnresult; |
51 | | - } |
52 | | -result.add(insertPosition +i,insertNumber +i); |
53 | | -if ((insertNumber +i) %10 ==0 && (insertNumber +i) == (insertNumber +10)) { |
54 | | -break; |
55 | | - } |
56 | | - } |
57 | | -while ((insertNumber +i) %10 !=0 && (insertNumber +i) <=n) { |
58 | | -result.add(insertPosition +i,insertNumber +i); |
59 | | -i++; |
60 | | - } |
61 | | -//find next insert position: |
62 | | -insertPosition =result.indexOf((insertNumber +i) /10); |
63 | | -returnaddNumbers(result,insertNumber +i,insertPosition +1,n); |
64 | | - } |
65 | | - |
66 | | -publicstaticvoidmain(String...strings) { |
67 | | -longlStartTime =newDate().getTime(); |
| 17 | +publicstaticclassSolution1 { |
| 18 | +//Radix sort doesn't apply here! Don't confuse yourself! |
68 | 19 |
|
69 | | -// CommonUtils.printList(lexicalOrder_TLE_by_23489(23489)); |
70 | | -// List<Integer> result = lexicalOrder(1);//right |
71 | | -// List<Integer> result = lexicalOrder(13);//right |
72 | | -// List<Integer> result = lexicalOrder_LTE_by_10458(58); |
73 | | -// List<Integer> result = lexicalOrder(120);//right |
74 | | -// List<Integer> result = lexicalOrder(1200); |
75 | | -// List<Integer> result = lexicalOrder(10); |
76 | | -// List<Integer> result = lexicalOrder(5000000); |
77 | | -// List<Integer> result = lexicalOrder_LTE_by_10458(50000);//this can finish in 183 ms |
78 | | -List<Integer>result =lexicalOrder_LTE_by_10458(500000); |
79 | | -// List<Integer> result = lexicalOrder_LTE_by_10458(14959); |
80 | | -longlEndTime =newDate().getTime(); |
81 | | -longdifference =lEndTime -lStartTime; |
82 | | -System.out.println("Elapsed milliseconds: " +difference); |
83 | | -System.out.println("result size is: " +result.size()); |
84 | | -// CommonUtils.printList(result); |
85 | | - } |
86 | | - |
87 | | -/** |
88 | | - * The most naive way is to generate this list, sort it using a customized comparator and then return it. |
89 | | - * Unfortunately, this results in TLE with this input: 23489 |
90 | | - */ |
91 | | -publicstaticList<Integer>lexicalOrder_TLE_by_23489(intn) { |
92 | | -List<Integer>result =newArrayList(); |
93 | | -for (inti =1;i <=n;i++) { |
94 | | -result.add(i); |
| 20 | +//rewrote their solution from Python to Java:https://discuss.leetcode.com/topic/54986/python-memory-limit-exceeded-for-problem-386/17 |
| 21 | +publicList<Integer>lexicalOrder(intn) { |
| 22 | +List<Integer>result =newArrayList(); |
| 23 | +inti =1; |
| 24 | +while (true) { |
| 25 | +result.add(i); |
| 26 | +if (i *10 <=n) { |
| 27 | +i *=10; |
| 28 | + }else { |
| 29 | +while (i %10 ==9 ||i ==n) { |
| 30 | +i /=10; |
| 31 | + } |
| 32 | +if (i ==0) { |
| 33 | +returnresult; |
| 34 | + } |
| 35 | +i++; |
95 | 36 | } |
96 | | -Collections.sort(result,newComparator<Integer>() { |
97 | | -@Override |
98 | | -publicintcompare(Integero1,Integero2) { |
99 | | -Strings1 =String.valueOf(o1); |
100 | | -Strings2 =String.valueOf(o2); |
101 | | -returns1.compareTo(s2); |
102 | | - } |
103 | | - }); |
104 | | -returnresult; |
| 37 | + } |
105 | 38 | } |
106 | | - |
| 39 | + } |
107 | 40 | } |