• 李皮皮皮皮皮
    2019-02-06
    各种排序算法真要说起来实际中使用的最多的也就是快排了。然而各种编程语言内置的标准库都包含排序算法的实现,基本没有自己动手实现的必要。然后作为经典的算法,自己实现一遍,分析分析时间空间复杂度对自己的算法设计大有裨益。需要注意的是为了高效,在实际的实现中,多种排序算法往往是组合使用的。例如c标准库中总体上是快排,但当数据量小于一定程度,会转而使用选择或插入排序。
    求平方根使用牛顿法二分逼近😄
    
     5
  • TryTs
    2019-02-07
    虽然现在有很多排序算法自己不会亲自写,但是作为算法的基础,分治,归并,冒泡等排序算法在时间复杂度,空间复杂度以及原地排序这些算法知识上的理解非常有帮助。递归分治这些算法思想在简单的算法中也能体现出来,其实更多的是思维方式的训练。

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    
     3
  • 虎虎❤️
    2019-02-07
    基本排序算法的关注点分为:
    1. 时间复杂度。如n的平方(冒泡,选择,插入);插入排序的优化希尔排序,则把复杂度降低到n的3/2次方;n乘以logn(快排,归并排序,堆排序)。
    2. 是否为原地排序。如,归并排序需要额外的辅助空间。
    3. 算法的稳定性。稳定排序(by nature)如冒泡,插入,归并。如果把次序考虑在内,可以把其他的排序(如快排,堆排序)也实现为稳定排序。
    4. 算法的实现。同为时间复杂度同为n平方的算法中,插入排序的效率更高。但是如果算法实现的不好,可能会降低算法的效率,甚至让稳定的算法变得不稳定。又如,快速排序有不同的实现方式,如三路快排可以更好的应对待排序数组中有大量重复元素的情况。堆排序可以通过自上而下的递归方式实现,也可以通过自下而上的方式实现。
    5. 不同算法的特点,如对于近乎有序的数组进行排序,首选插入排序,时间复杂度近乎是n,而快速排序则退化为n平方。

    二分查找,需要注意 (l+r)/2可能存在越界问题。

    leetcode题,用二分查找找到x*x > n 且(x-1)的平方小于n的数,则n-1就是结果。或者 x的平方小于n且x+1的平方大于n,则返回x。
    展开
    
     2
  • 失火的夏天
    2019-02-06
    牛顿法或者二分逼近都可以解决平方根问题,leetcode上有些大神的思路真的很厉害,经常醍醐灌顶
    
     2
  • hopeful
    2019-02-16
    #O(n)时间复杂度时间复杂度内找到一组数据的第 n大元素
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a
    def QuickSort(n):
        array = Array(100)
        if n > len(array) or n < 1:
            print("超出范围,找不到")
            return
        n = n-1
        a = qsort(0 , len(array)-1 , array , n)
        print(sorted(array))
        print("-----------------------------")
        print(a)

    def qsort(start , end , array , n):
        if start == end:
            res = array[start]
        if start < end:
            key = partation(array , start , end)
            print(start , key , end)
            if key > n :
                res = qsort(start , key-1 , array , n)
            elif key < n:
                res = qsort(key+1 , end , array , n)
            else:
                res = array[key]
        return res

    def swap(array , start , end):
        temp = array[start]
        array[start] = array[end]
        array[end] = temp

    def partation(array , start , end):
        temp = array[start]
        while start < end :
            while start<end and array[end]<=temp:
                end-=1
            swap(array , start , end)
            while start<end and array[start]>=temp:
                start+=1
            swap(array , start , end)
        return start
    展开
    
     1
  • Monster
    2019-02-13
    /**
     * O(n)时间复杂度内求无序数组中第K大元素
     */
    public class TopK {

        public int findTopK(int[] arr, int k) {
            return findTopK(arr, 0, arr.length - 1, k);
        }

        private int findTopK(int[] arr, int left, int right, int k) {
            if (arr.length < k) {
                return -1;
            }
            int pivot = partition(arr, left, right);
            if (pivot + 1 < k) {
                findTopK(arr, pivot + 1, right, k);
            } else if (pivot + 1 > k) {
                findTopK(arr, left, pivot - 1, k);
            }
            return arr[pivot];
        }


        private int partition(int[] array, int left, int right) {
            int pivotValue = array[right];
            int i = left;

            //小于分区点放在左边 大于分区点放在右边
            for (int j = left; j < right; j++) {
                if (array[j] < pivotValue) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    i++;
                }
            }
            //与分区点交换
            int tmp = array[i];
            array[i] = array[right];
            array[right] = tmp;
            return i;
        }
    }
    展开

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您10元无门槛优惠券,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

     1
     1
  • EidLeung
    2019-02-12
    编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素。
    这个的时间复杂路应该是n·logk吧?
    
     1
  • abner
    2019-02-11
    java实现冒泡排序
    代码如下:
    package sort;

    public class BubbleSort {

        public int[] bubbleSort(int[] array) {
            for (int i = 0;i < array.length - 1;i++) {
                for (int j = 0;j < array.length - i - 1;j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                }
            }
            return array;
        }

        public static void main(String[] args) {
            int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            BubbleSort bubbleSort = new BubbleSort();
            int[] result = bubbleSort.bubbleSort(array);
            for (int i = 0;i < result.length;i++) {
                System.out.print(result[i] + " ");
            }
        }

    }
    展开
    
     1
  • kai
    2019-02-11
    实现模糊二分查找算法2:

    public class BinarySearch {
        // 3. 查找第一个大于等于给定值的元素
        public static int bsFistGE(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] >= target) {
                    if (mid == 0 || array[mid-1] < target) {
                        return mid;
                    } else {
                        hi = mid - 1;
                    }
                } else {
                    lo = mid + 1;
                }
            }

            return -1;
        }

        // 4. 查找最后一个小于等于给定值的元素
        public static int bsLastLE(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] <= target) {
                    if (mid == hi || array[mid+1] > target) {
                        return mid;
                    } else {
                        lo = mid + 1;
                    }
                } else {
                    hi = mid - 1;
                }
            }

            return -1;
        }
    }
    展开
    
     1
  • kai
    2019-02-11
    实现模糊二分查找算法1:

    public class BinarySearch {
        
        // 1. 查找第一个值等于给定值的元素
        public static int bsFirst(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    if (mid == lo || array[mid-1] != array[mid]) {
                        return mid;
                    } else {
                        hi = mid - 1;
                    }
                }
            }

            return -1;
        }

        // 2. 查找最后一个值等于给定值的元素
        public static int bsLast(int[] array, int target) {
            int lo = 0;
            int hi = array.length - 1;

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    if (mid == hi || array[mid] != array[mid+1]) {
                        return mid;
                    } else {
                        lo = mid + 1;
                    }
                }
            }

            return -1;
        }
    }
    展开
    
     1
  • kai
    2019-02-11
    实现一个有序数组的二分查找算法:

    public class BinarySearch {
        // 最简单的二分查找算法:针对有序无重复元素数组
        // 迭代
        public static int binarySearch(int[] array, int target) {
            if (array == null) return -1;

            int lo = 0;
            int hi = array.length-1; // 始终在[lo, hi]范围内查找target

            while (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1); // 这里若是 (lo + hi) / 2 有可能造成整型溢出

                if (array[mid] > target) {
                    hi = mid - 1;
                } else if (array[mid] < target) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }

            return -1;
        }

        // 递归
        public static int binarySearchRecur(int[] array, int target) {
            if (array == null) return -1;
            return bs(array, target, 0, array.length-1);
        }

        private static int bs(int[] array, int target, int lo, int hi) {
            if (lo <= hi) {
                int mid = lo + ((hi - lo) >> 1);
                if (array[mid] > target) {
                    return bs(array, target, lo, mid-1);
                } else if (array[mid] < target) {
                    return bs(array, target, mid+1, hi);
                } else {
                    return mid;
                }
            }

            return -1;
        }
    }
    展开
    
     1
  • 纯洁的憎恶
    2019-02-09
    这道题似乎可以等价于从1到x中找到一个数y,使得y*y小于等于x,且(y+1)*(y+1)大于x。那么可以从1到x逐个尝试,提高效率可以采用二分查找方法,时间复杂度为O(logx)。
    
     1
  • 黄丹
    2019-02-07
    王争老师初三快乐!
    这是今天两道题的解题思路和代码
    1. O(n)时间内找到第K大的元素:
    解题思路:利用快排中分区的思想,选择数组区间A[0...n-1]的左右一个元素A[n-1]作为pivot,对数组A[0...n-1]原地分区,这样数组就分成了三部分,A[0..p-1],A[p],A[p+1...n-1],如果p+1=k,那么A[p]就是要求解的元素,如果K>p+1,则说明第K大的元素在A[p+1...n-1]这个区间,否则在A[0...p-1]这个区间,递归的查找第K大的元素
    2. Sqrt(x) (x 的平方根)
    解题思路:利用二分查找的思想,从1到x查找x的近似平方根
    代码:
    https://github.com/yyxd/leetcode/blob/master/src/leetcode/sort/Problem69_Sqrt.java
    展开
    
     1
  • C_love
    2019-02-07
    Use Binary Search

    class Solution {
        public int mySqrt(int x) {
            if (x == 0 || x == 1) {
                return x;
            }
            
            int start = 0;
            int end = (x >> 1) + 1;
            
            while (start + 1 < end) {
                final int mid = start + ((end - start) >> 1);
                final int quotient = x / mid;
                if (quotient == mid) {
                    return mid;
                } else if (quotient < mid) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
            
            return start;
        }
    }
    展开

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    
     1
  • Geek_86533a
    2019-08-14
    不断学习,不断练习到今天。发现自己的代码能力、思考问题的能力有了明显的进步。感谢!
    
    
  • 懒猫
    2019-05-23
    打卡
    
    
  • hopeful
    2019-02-17
    #二分查找变种
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a
    #查找第一个值等于给定值的元素
    def find_1(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                if mid==0 or array[mid] != array[mid-1]:
                    return mid
                else:
                    right = mid - 1
        print("找不到")
        return -1

    #查找最后一个值等于给定值的元素
    def find_2(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                if mid==right or array[mid] != array[mid+1]:
                    return mid
                else:
                    left = mid + 1
        print("找不到")
        return -1

    #查找第一个值大于等于给定值的元素
    def find_3(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] >= n:
                if mid==0 or array[mid-1]<n:
                    return mid
                else:
                    right = mid - 1
            else array[mid] < n:
                left = mid + 1
        print("找不到")
        return -1

    #查找最后一个值小于等于给定值的元素
    def find_4(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] <= n:
                if mid==right or array[mid+1]>n:
                    return mid
                else:
                    left = mid + 1
            else array[mid] > n:
                right = mid - 1
        print("找不到")
        return -1
    展开
    
    
  • hopeful
    2019-02-16
    #实现一个有序数组的二分查找算法
    import random
    import time

    def Array(n):
        a = []
        for i in range(n):
            a.append(random.randint(0 , n))
        return a

    def find(n):
        array = Array(100)
        array = sorted(array)
        left = 0
        right = len(array)-1
        while left <= right:
            mid = int((left+right)/2)
            if array[mid] > n:
                right = mid - 1
            elif array[mid] < n:
                left = mid + 1
            else:
                return mid
        print("找不到")
        return -1
    展开
    
    
  • 拉欧
    2019-02-15
    x 的平方根 go 语言实现
    func mySqrt(x int) int{

        if x==0{
            return 0
        }
        min:=1
        max:=x

        for {
            mid:=min+(max-min)/2
            if mid*mid==x{
                return mid
            }else if mid*mid<x{
                if (mid+1)*(mid+1)>x{
                    return mid
                }else{
                    min=mid+1
                }
            }else{
                max=mid-1
            }

        }
    }
    展开
    
    
  • TryTs
    2019-02-14
    #include<iostream>
    #include<cmath>
    using namespace std;
    double a = 1e-6;
    double sqrt(double n){
        double low = 0.0;
        double high = n;
        
    int i = 1000;

        while(i--){
            double mid = low + (high - low) / 2.0;
            //cout<<"n:"<<n<<endl;
            double square = mid * mid;
            //cout<<"sq:"<<square<<endl;
            //cout<<"s:"<<abs(square - n)<<endl;
            if(abs(mid * mid - n) < a){
                return mid;
            }
            else{

                if(square > n){
                    high = mid;
                }
                else{
                 low = mid;
                }
            }
        }
        return -2.0;
    }
    int main(){
        double t;
        while(true){
            cin>>t;
            cout<<sqrt(t)<<endl;
        }
    }
    展开
    
    
我们在线,来聊聊吧