首页 > 试题广场 >

字典序排列

[编程题]字典序排列
  • 热度指数:463 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个正整数,按字典序返回 [1,n] 内的正整数。

数据范围:
示例1

输入

5

输出

[1,2,3,4,5]
示例2

输入

10

输出

[1,10,2,3,4,5,6,7,8,9]
#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;    
    }
};

发表于 2023-05-26 11:25:52 回复(0)
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
}

发表于 2023-03-15 21:37:01 回复(0)
//数字首位是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);
        }
    }

发表于 2023-02-15 14:28:54 回复(0)
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;
    }
};

发表于 2022-12-07 15:09:50 回复(0)
# -*- 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

发表于 2022-06-26 09:04:09 回复(0)
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;
    }
}

发表于 2022-05-25 20:13:09 回复(0)