排序和二分查找sqrtx-leetcode练习题

青旅半醒 2023-07-19 05:48 2阅读 0赞

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    class Solution {
        /**
         * 实现 int sqrt(int x) 函数。
         * <p>
         * 计算并返回 x 的平方根，其中 x 是非负整数。
         * <p>
         * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode-cn.com/problems/sqrtx
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         * @param x
         * @return
         */
        public int mySqrt(int x) {
            if (x < 2) {
                return x;
            }
            int left = 2;
            int right = x / 2;
            int mid = x;
            long num = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                num = (long) mid * mid;
                if (num > x) {
                    right = mid - 1;
                } else if (num < x) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return right;
        }
    
        public static void main(String[] args) throws IOException {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String line;
            while ((line = in.readLine()) != null) {
                int x = Integer.parseInt(line);
                int ret = new Solution().mySqrt(x);
                String out = String.valueOf(ret);
                System.out.print(out);
            }
        }
    }

解题思路：

二分查找，不断减少查找范围。

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关排序和二分查找sqrtx-leetcode练习题

import java.io.BufferedReader; import java.io.IOException; import java.io.In

青旅半醒/ 2023年07月19日 05:48/ 0 赞/ 3 阅读

相关 C语言基础练习题--二分查找

题目在排序数组中查找元素的第一个和最后一个位置给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

旧城等待，/ 2022年12月25日 12:56/ 0 赞/ 123 阅读

相关冒泡排序`交换排序·二分查找

public class ArrayTest \{ public static void main(String\[\] args) \{ int\[\] a = ne

雨点打透心脏的1/2处/ 2022年08月08日 12:51/ 0 赞/ 163 阅读

相关 c语言快速排序和二分查找模型

引言： c语言中 stdlib 自定义了一个 qsort 快速排序函数模型： int cmp(const void \a,const void \b)

柔情只为你懂/ 2022年08月02日 05:40/ 0 赞/ 150 阅读

相关 Java数组中的排序和二分查找

【题目】建立一个关于日期的类，其中包括日期比较的类，并且重写toString方法。在main函数中创建一个find()方法，利用二分查找的方法找出日期，若有则返回其在数组中

男娘i/ 2022年06月02日 11:21/ 0 赞/ 183 阅读

相关冒泡排序与二分查找

冒泡排序：冒泡排序的核心思想是用第一个数依次与以后的数比较，如果有比它大或者比它小的就与它交换位置，那么第一个得到的数就是最大或者最小的；同理用第二个数再执行依次，，，依次

Bertha 。/ 2022年05月18日 11:10/ 0 赞/ 165 阅读

相关二分查找和排序

二分查找，主要是针对排序问题进行查找 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

柔光的暖阳◎/ 2022年05月14日 15:25/ 0 赞/ 202 阅读

相关 JAVA 排序与二分查找

排序与二分查找冒泡排序排序思想：从前往后将相邻的两个元素进行比较，则第一次比较完成后，最后一个元素一定是数值最大的。依次重复，每一轮比较就会将剩余元素中的最大一

谁践踏了优雅/ 2022年05月04日 08:30/ 0 赞/ 190 阅读

相关字符串二分查找、快速排序

public class Main { / 字符串的二分查找 @param str @par

Dear 丶/ 2022年03月18日 06:24/ 0 赞/ 186 阅读

相关冒泡排序和二分查找

有序数组二分查找实现： public class BinarySearch{ / int midArray = (righ

深碍√TFBOYSˉ_/ 2022年01月27日 07:35/ 0 赞/ 203 阅读