n个数的逆序数（LeetCode-400. 第N位数字）

题目来源

400. 第 N 位数字

题目详情

给你一个整数 n     
    
    
    
，请你在无限的整数序列[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第n 位上的数字    
    
    
    
 。

示例 1：

输入：

n = 3

输出： 3

示例 2：

输入：

n = 11

输出：

0

解释： 第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0      


     


     


     


 ，它是 10 的一部分


     


     


     


     。

提示：

1 <= n <= 231 - 1

题解分析

本题的解题关键是如何定位到指定字符所在的数字
 




 




 




 




。通过仔细观察序列数字串




 




 




 




 ，可以发现
   

   

   

   

，位数为1的数字个数为9     

     

     

     

，位数为2的数字个数为90 




  




  




  




  ，位数为3的数字个数为900

  


  


  


  

，依次类推   

   

   

   

。

按照上述规律     
     
     
     
，可以进一步每种位数中包含的字符个数  




   




   




   




  ，它们是数字个数与位数的乘积 

     

     

     

     。通过这种模拟法


 



 



 



 

，可以首先求出所述字符是哪种位数的                    ，进而根据除余运算可以计算出这个数字的具体指

  




  




  




  



。最后   




    




    




    




  ，问题就转换为了求解某个具体数字的某位上的字符  


  


  


  


。

算法实现

class Solution { public int findNthDigit(int n) { // 9 * 1, 90 * 2, 900 * 3, 9000 * 4 int bit = 1; long cnt = 9; while (bit * cnt < n) { n -= bit * cnt; bit++; cnt = cnt * 10; } // rest表示在bit位数集中的第几字符位




















，减一是为了下标从0开始计算 int rest = (int) (n - 1); // start表示bit位数集中的起始元素 int start = (int) Math.pow(10, bit-1); // n是bit位数集中的第几个元素 int pt = rest / bit; // num表示第n个字符所在的元素 int num = start + pt; // seq表示对应元素的第几个字符（从左往右） int seq = rest % bit; // 后续问题转换为求num数字的第seq个字符是什么                    ，1203 // 去除第seq个字符后面数字后的结果 int left = num / (int) Math.pow(10, bit - seq -1); return left % 10; } }