一个长度为为偶数的数组，每一个段落长度为奇数，且每个段落的中位数相同，要求判断是否存在分割的方法，个人判断复杂度需要O(N log N)

Question

一个长度为为偶数的数组，要将其分为几个段落，每一个段落长度为奇数，且每个段落的中位数相同，要求判断是否存在分割的方法，个人判断复杂度需要O(N log N)，怎么实现？

Answer 1

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7414205
• 这篇博客你也可以参考下：在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
• 除此之外, 这篇博客: 440. 字典序的第K小数字中的 解法二：优化遍历字典树模拟 O(log^2(n)) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  我们可以看到前面模拟前序遍历会超时，因为O(n)太大，那么我们考虑是否可以省去遍历所有节点，有以下思路：

  • 计算每个节点其子树的节点数量
  • 如果当前k值比此子树的数量少或者等于，那么一定存在于此子树
  • 如果当前k值比此子树的数量多，那么他一定存在于此节点右侧的节点

  这里关键就是如何计算每个节点其子树的节点数量：

  • 我们可以一次计算一层的节点数，通过左右的节点值计算
  • 已知最左边的节点为left，最右侧的节点为right，那么一层的节点数量为min(right, n) left + 1, 注意一层的最右边节点不能超过最大值
  • 移到下一层即，left10即可，右节点right10会变成其最左子节点，还需要+9
  • 整个计算循环到层的left比n大自动跳出

  时间复杂度： 可以看到计算节点数为log(n),跳跃遍历树也是log(n)，即 O(log^2(n))

  class Solution {
  public:
      int getAllNodes(int root,long n){
          // 获取包含自己的所有节点数目
          int ans = 0;
          long left = root;
          long right = root;
          while(left <= n){
              ans += min(right, n) - left + 1;
              left *= 10;
              right = right*10+9;
          }
          return ans;
      }
  
      int findKthNumber(int n, int k) {
          int ans;
          long root = 1;
          while(k>0){
              cout<<root<<" ";
              if(getAllNodes(root,n) >= k){
                  // k 包含在其子树,k减去此节点，向下走 
                  k--;
                  if(k==0) break;
                  root *= 10;
              }else if(getAllNodes(root,n) < k){
                  // 在其右边,减去当前节点与其子节点，向右走
                  k-=getAllNodes(root,n);
                  root ++;
              }
          }
          return root;
      }
  };
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^