给定一个正整数,按字典序返回 [1,n] 内的正整数。
数据范围:
#include <algorithm> #include <map> #include <string> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型vector */ vector<int> orderArray(int n) { // write code here map<string, int>Hash; for(int i=0; i<n;i++) { string str; str = to_string(i+1); Hash[str] = i+1; } vector<int> output; for (auto item: Hash) output.push_back(item.second); return output; } };
package main import "sort" import "strconv" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型一维数组 */ func orderArray(n int) []int { arr := make([]int, n) for i, _ := range arr { arr[i] = i + 1 } sort.Slice(arr, func(i, j int) bool { return strconv.Itoa(arr[i]) < strconv.Itoa(arr[j]) }) return arr }
//数字首位是1或者2、3、4...,分成9个大的层次,字典序排列就是分别从每一层次向后排列到底(此处范围判定只有是否超过n这个条件),然后再排列下一层次的数据,属于深度优先搜索 ArrayList<Integer> list = new ArrayList<>(); public ArrayList<Integer> orderArray (int n) { //判断n小于10时,就是简单的顺序排列,这步其实可以不要 if(n<10){ for(int i=1;i<=n;i++){ list.add(i); } }else{ for(int i=1;i<10;i++){ dfs(i,n); } } return list; } public void dfs(int num,int n){ //边界判定,每个层次的数据是否超过n,超过就返回不排列 if(num > n){ return; } list.add(num); for(int i=0;i<10;i++){ dfs(num*10+i,n); } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型vector */ static bool cmp(int a, int b){ string A = to_string(a); string B = to_string(b); return A < B; } vector<int> orderArray(int n) { // write code here vector<int> v; for(int i=1; i<=n; i++){ v.push_back(i); } sort(v.begin(), v.end(), cmp); return v; } };
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param n int整型 # @return int整型一维数组 # class Solution1: """ 题目: https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 算法: 字符串排序 复杂度: 时间复杂度:O(nlogn) 空间复杂度:O(n) """ def orderArray(self, n): # write code here strNums = [str(i) for i in range(1, n + 1)] strNums.sort() return map(int, strNums) class Solution: """ 题目: https://www.nowcoder.com/practice/de49cf70277048518314fbdcaba9b42c?tpId=196&tqId=40452&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 参考: 大神:唐喻铭 算法: 字典树 初始:num = 1 按照字典序规律:1 -> 10 -> 100 ...直到大于n时,从*10变为+1操作,这里需要注意的是:如果个位数是9,那么再+1,就需要进位,比如9 + 1 -> 2;或者num + 1 > n,也需要进位处理 比如n = 28: 1,10,11,12,13,...,19 下一个数组为2,而不是20 1,10,11,...,19,2,20,21,...,28 下一个数字为3,而不是29 复杂度: 时间复杂度:O(n) 空间复杂度:O(1) """ def orderArray(self, n): # write code here res, num = [], 1 for i in range(n): res.append(num) if num * 10 <= n: num *= 10 else: while num % 10 == 9&nbs***bsp;num + 1 > n: num /= 10 num += 1 return res if __name__ == "__main__": sol = Solution() # n = 5 # n = 10 n = 28 res = sol.orderArray(n) print res
import java.util.*; public class Solution { //如果num*10后比n小,那么num*10就是下一个要放入list中的数 //如果num*10后比n大,那么就num++,其结果就是下一个要放入list中的数 //如果num的个位数为9或者num+1>n,说明需要进行进位操作,num=num/10,num++ //比如n为28 //num=19的话,就需要进位,即num/10后的结果加一,下一位数2 //num=28的话,也需要进位,即num/10后的结果加一,下一位数3 //一共需要向list中添加n次数字 public ArrayList<Integer> orderArray (int n) { ArrayList<Integer> list = new ArrayList<>(); int num = 1; for(int i = 0;i < n;i ++) { list.add(num); if(num * 10 <= n) { num *= 10; }else { while((num % 10 == 9) || (num + 1 > n)) { num /= 10; } num ++; } } return list; } }