leetcode 400. Nth Digit | 400. 第 N 位数字（二分法找左侧不大于n的第一个数）

我会带着你远行 2022-08-29 09:41 118阅读 0赞

## 题目 ##

[https://leetcode.com/problems/nth-digit/][https_leetcode.com_problems_nth-digit]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

本题考察 Math， Binary Search。思路不难，需要扣边界细节。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int findNthDigit(int n) { 
            // [1,n] 二分找左侧不大于n的第一个数
            int L = 1;
            int R = n;
            int nearLeft = -1;
            int count;
            while (L <= R) { 
                int M = L + ((R - L) >> 1);
                count = countDigit(M);
                if (count <= n - 1) { 
                    nearLeft = M;
                    L = M + 1;
                } else { 
                    R = M - 1;
                }
            }
            return String.valueOf(nearLeft).charAt(n - countDigit(nearLeft) - 1) - '0';
        }
    
        public int countDigit(int n) { 
            int count = 0;
            int multi = 1;
            while (n / Math.pow(10, multi) > 1) { 
                count += (9 * Math.pow(10, multi - 1) * multi);
                multi++;
            }
            count += ((n - Math.pow(10, multi - 1)) * multi);
            return count;
        }
    }

二分找左侧不大于 n 的第一个数：

public int binSearch(ArrayList<Integer> list, int target) { 
            int left = 0, right = list.size() - 1;
            while (left <= right) { 
                int mid = (left + right) / 2;
                if (list.get(mid) == target)
                    return mid;
                if (list.get(mid) > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            return right;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_nth-digit]: https://leetcode.com/problems/nth-digit/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/ece473185bfb4101befb17a9bde458ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/843c41913bd04e9e9b4f9949189cafe1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/7e21075fdbe64a768d0a8d7b879ea767.png