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