有道难题2的搞笑解，时间复杂度O(1)-阿里云开发者社区

有道难题2的搞笑解，时间复杂度O(1)

2016-08-01 836

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

经典查表法

        static int[] arr;

        static T2()
        {
            arr = new int[1593];
            arr[0] = 1729;
            arr[1] = 4104;
            arr[2] = 13832;
            arr[3] = 20683;
            arr[4] = 32832;
            arr[5] = 39312;
            arr[6] = 40033;
            arr[7] = 46683;
            .........
            arr[1585] = 1156658048;
            arr[1586] = 1167270776;
            arr[1587] = 1181984832;
            arr[1588] = 1217741768;
            arr[1589] = 1228225789;
            arr[1590] = 1231216119;
            arr[1591] = 1234859661;
            arr[1592] = 1477354411;
        }

        public static int count(int n)
        {
            int max = 1592;
            int min = 0;
            int cur=0;
            while (max >= min)
            {
                cur = (max + min) / 2;
                if (n < arr[cur])
                {
                    max = cur - 1;
                }
                else if (n > arr[cur])
                {
                    min = cur + 1;
                }
                else
                {
                    break;
                }
            }
            if (max < min)
            {
                cur = max;
            }
            return cur+1;
        }