解题思路

递归 将时间复杂度降到logn

代码

###cpp

class Solution {
private:
    char ch_not(char ch) {
        if(ch == '0') { return '1'; }
        else          { return '0'; }
    }
public:
    char findKthBit(int n, int k) {
        if(n == 1) { return '0'; }
        int mid = (1<<(n-1));
        if(k == mid) { return '1'; }
        if(k < mid) { return findKthBit(n-1, k); }
        return ch_not(findKthBit(n-1, (1<<n) - k)); 
    }
};