In this Leetcode Lexicographical Number problem solution you have given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order. You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Problem solution in Python.
class Solution: def lexicalOrder(self, n: int) -> List[int]: l = list() for i in range(1,n+1): l.append(str(i)) l.sort() i = len(l)-1 while i>0: l[i] = int(l[i]) i-=1 l[i] = int(l[i]) return l
Problem solution in Java.
public List<Integer> lexicalOrder(int n) { int num = 1; List<Integer> results = new ArrayList<>(); while (true) { if (num <= n) { results.add(num); num *= 10; continue; } num /= 10; while (num % 10 == 9 && num != 0) num /= 10; if (num == 0) return results; num += 1; } }
Problem solution in C++.
class Solution { int next(int last, int n) { if (last * 10 <= n) return last * 10; if (last == n) last /= 10; ++last; while(last % 10 == 0) last /= 10; return last; } public: vector<int> lexicalOrder(int n) { if (n < 1) return vector<int>(); vector<int> result(n); result[0] = 1; for (int i = 1; i < n; ++ i) result[i] = next(result[i - 1], n); return result; } };
0 Comments