求最大公约数

写一段代码，求出两个整数的最大公约数，要尽量优化算法的性能。

辗转相除法， 又名欧几里得算法（Euclidean algorithm），该算法的目的是求出两个正整数的最大公约数。它是已知最古老的算法， 其产生时间可追溯至公元前300年前。

两个数的最大公约数,将其中一个数加到另一个数上,得到的新数,其公约数不变,比如(4,6)=(4+6,6)=(4,6+2×4)=2

解题代码：

#include<iostream> 

using namespace std;

int fun(int m,int n){
	return n ? fun(n,m%n) : m ;
}

int main(){
	int a,b;
	cin>>a>>b;	
	cout<<fun(a,b)<<endl;
	return 0;
}

一行代码解决了？太强了本文引用来源：

• 求最大公约数（辗转相除法）_ACfun-CSDN博客_辗转相除法求最大公约数

判断一个数是不是2的整数次幂

2的整数次幂有4、8、16、32等，但是把它们转化为二进制数后减1会1发现所有位都是1.

所以凡是2的整数次幂和它本身减1的结果进行与运算，其结果必然为0！

解题代码：

int main(){
    int a;
    cin>>a;
    if ((a&a-1) == 0)
    	cout<<"yes"<<endl;
    else
    	cout<<"no"<<endl;
	return 0;
}

ps：时间复杂度为O（1）哦！

无序数组排序后最大相邻差

1.利用桶排序的思想，先求出原数组从最小值Min到最大值Max的单位区间长度d，d=(Max-Min)/n-1。算出d的作用是为了后续确定各个桶的区间范围划分。

2.创建一个长度是N+1的数组Array，数组的每一个元素都是一个List，代表一个桶。

3.遍历原数组，把原数组每一个元素插入到新数组Array对应的桶当中，进入各个桶的条件是根据不同的数值区间。由于桶的总数量是N+1，所以至少有一个桶是空的。

4.遍历新数组Array，计算每一个空桶右端非空桶中的最小值，与空桶左端非空桶的最大值的差，数值最大的差即为原数组排序后的相邻最大差值。

public static int getMaxSortedDistance(int[] array) {
        // 1. 获取数组中的最大值和最小值，构建数组的长度
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        int distance = max - min;
        // 如果max和min相等，说明数组所有元素都相等，返回0
        if (distance == 0) {
            return 0;
        }
        // 2. 初始化桶
        int bucketNum = array.length;
        Bucket[] buckets = new Bucket[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = new Bucket();
        }
 
        // 3. 遍历原始数组，确定每个桶的最大最小值
        for (int i = 0; i < array.length; i++) {
            // 确定数组元素所属的桶小标
            int index = ((array[i] - min) * (bucketNum - 1)) / distance;
            if (buckets[index].min == null || buckets[index].min > array[i]) {
                buckets[index].min = array[i];
            }
            if (buckets[index].max == null || buckets[index].max < array[i]) {
                buckets[index].max = array[i];
            }
        }
 
        // 4. 遍历桶，找到最大差值
        // 这里采用临时变量leftMax,在每一轮迭代时存储当前左侧桶的最大值，
        // 而两个桶之间的差值，则是buckets[i].min - leftIndex
        int leftIndex = buckets[0].max;
        int maxDistance = 0;
        for (int i = 1; i < buckets.length; i++) {
            if (buckets[i].min == null) {
                continue;
            }
            if (buckets[i].min - leftIndex > maxDistance) {
                maxDistance = buckets[i].min - leftIndex;
            }
            leftIndex = buckets[i].max;
        }
        return maxDistance;
 
    }
 
    /**
     * 桶
     */
    private static class Bucket{
        Integer min;
        Integer max;
    }
 
public static void main(String[] args) {
 
        int[] array = new int[] {2, 6, 3, 4, 5, 10, 3};
//        int[] array = new int[]{0, 0, 1, 2, 3, 4, 5, 6, 12, 13, 20, 10};
        // 桶排序方式
        int maxSortedDistance = getMaxSortedDistance(array);
        System.out.println("最大相邻差为:"+ maxSortedDistance);
 
    }