Question

2802. 找出第 K 个幸运数字

English Version

题目描述

我们知道 4 和 7 是 幸运 数字。同时，如果一个数字只包含幸运数字，那么它被称为幸运数字。

给定一个整数 k，返回第 k 个幸运数字，并将其表示为一个 字符串 。

 

示例 1：

输入：k = 4
输出："47"
解释：第一个幸运数字是 4，第二个是 7，第三个是 44，第四个是 47。

示例 2：

输入：k = 10
输出："477"
解释：按递增顺序列出的幸运数字为：
4, 7, 44, 47, 74, 77, 444, 447, 474, 477。 因此第10个幸运数字是477。

示例 3：

输入：k = 1000
输出："777747447"
解释：第 1000 个幸运数字是 777747447。

 

提示：

• 1 <= k <= 109

解法

方法一：数学

根据题目描述，一个幸运数只包含数字 $4$ 和 $7$，因此 $n$ 位幸运数的个数为 $2^n$。

我们初始化 $n=1$，接下来循环判断 $k$ 是否大于 $2^n$，如果大于则将 $k$ 减去 $2^n$，同时 $n$ 加一，直到 $k$ 小于等于 $2^n$。此时，我们只需要找出 $n$ 位幸运数中的第 $k$ 个即可。

如果 $k$ 小于等于 $2^{n-1}$，则第 $k$ 个幸运数的第一位为 $4$，否则第一位为 $7$，然后我们将 $k$ 减去 $2^{n-1}$，继续判断第二位，直到 $n$ 位幸运数的所有位都判断完毕。

时间复杂度 $O(\log k)$，空间复杂度 $O(\log k)$。

class Solution:
  def kthLuckyNumber(self, k: int) -> str:
    n = 1
    while k > 1 << n:
      k -= 1 << n
      n += 1
    ans = []
    while n:
      n -= 1
      if k <= 1 << n:
        ans.append("4")
      else:
        ans.append("7")
        k -= 1 << n
    return "".join(ans)

class Solution {
  public String kthLuckyNumber(int k) {
    int n = 1;
    while (k > 1 << n) {
      k -= 1 << n;
      ++n;
    }
    StringBuilder ans = new StringBuilder();
    while (n-- > 0) {
      if (k <= 1 << n) {
        ans.append('4');
      } else {
        ans.append('7');
        k -= 1 << n;
      }
    }
    return ans.toString();
  }
}

class Solution {
public:
  string kthLuckyNumber(int k) {
    int n = 1;
    while (k > 1 << n) {
      k -= 1 << n;
      ++n;
    }
    string ans;
    while (n--) {
      if (k <= 1 << n) {
        ans.push_back('4');
      } else {
        ans.push_back('7');
        k -= 1 << n;
      }
    }
    return ans;
  }
};

func kthLuckyNumber(k int) string {
  n := 1
  for k > 1<<n {
    k -= 1 << n
    n++
  }
  ans := []byte{}
  for n > 0 {
    n--
    if k <= 1<<n {
      ans = append(ans, '4')
    } else {
      ans = append(ans, '7')
      k -= 1 << n
    }
  }
  return string(ans)
}

function kthLuckyNumber(k: number): string {
  let n = 1;
  while (k > 1 << n) {
    k -= 1 << n;
    ++n;
  }
  const ans: string[] = [];
  while (n-- > 0) {
    if (k <= 1 << n) {
      ans.push('4');
    } else {
      ans.push('7');
      k -= 1 << n;
    }
  }
  return ans.join('');
}