Question

440. 字典序的第 K 小数字

English Version

题目描述

给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。

 

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

 

提示:

• 1 <= k <= n <= 109

解法

方法一

class Solution:
  def findKthNumber(self, n: int, k: int) -> int:
    def count(curr):
      next, cnt = curr + 1, 0
      while curr <= n:
        cnt += min(n - curr + 1, next - curr)
        next, curr = next * 10, curr * 10
      return cnt

    curr = 1
    k -= 1
    while k:
      cnt = count(curr)
      if k >= cnt:
        k -= cnt
        curr += 1
      else:
        k -= 1
        curr *= 10
    return curr

class Solution {
  private int n;

  public int findKthNumber(int n, int k) {
    this.n = n;
    long curr = 1;
    --k;
    while (k > 0) {
      int cnt = count(curr);
      if (k >= cnt) {
        k -= cnt;
        ++curr;
      } else {
        --k;
        curr *= 10;
      }
    }
    return (int) curr;
  }

  public int count(long curr) {
    long next = curr + 1;
    long cnt = 0;
    while (curr <= n) {
      cnt += Math.min(n - curr + 1, next - curr);
      next *= 10;
      curr *= 10;
    }
    return (int) cnt;
  }
}

class Solution {
public:
  int n;

  int findKthNumber(int n, int k) {
    this->n = n;
    --k;
    long long curr = 1;
    while (k) {
      int cnt = count(curr);
      if (k >= cnt) {
        k -= cnt;
        ++curr;
      } else {
        --k;
        curr *= 10;
      }
    }
    return (int) curr;
  }

  int count(long long curr) {
    long long next = curr + 1;
    int cnt = 0;
    while (curr <= n) {
      cnt += min(n - curr + 1, next - curr);
      next *= 10;
      curr *= 10;
    }
    return cnt;
  }
};

func findKthNumber(n int, k int) int {
  count := func(curr int) int {
    next := curr + 1
    cnt := 0
    for curr <= n {
      cnt += min(n-curr+1, next-curr)
      next *= 10
      curr *= 10
    }
    return cnt
  }
  curr := 1
  k--
  for k > 0 {
    cnt := count(curr)
    if k >= cnt {
      k -= cnt
      curr++
    } else {
      k--
      curr *= 10
    }
  }
  return curr
}