1.复杂度、对数器、二分法与异或运算-阿里云开发者社区

三大排序算法

通过使用对数器来检验，可以保证代码的正确性。

1）选择排序

package com.harrison.one;
import java.util.Arrays;
//选择排序
public class Class01_SelectionSort {
  // 选择排序核心代码
  public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    for (int i = 0; i < arr.length - 1; i++) {// i~N-1
      // 最小值在哪个位置上，i~N-1
      int minIdx = i;
      for (int j = i + 1; j < arr.length; j++) {// i~N-1上找最小值的下标
        minIdx = arr[j] < arr[minIdx] ? j : minIdx;
      }
      swap(arr, i, minIdx);
    }
  }
  // 交换两个元素
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  // 产生随机数组，长度随机，且值也随机
  public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
  }
  // copy数组
  public static int[] copyArray(int[] arr) {
    if (arr == null) {
      return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
      res[i] = arr[i];
    }
    return res;
  }
  // 写一个比较器的方法：系统提供的排序的方法，肯定是对的
  public static void comparator(int[] arr) {
    Arrays.sort(arr);
  }
  // 比较两个数组是否完全一样
  public static boolean isEqual(int[] arr1, int[] arr2) {
    if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
      return false;
    }
    if (arr1 == null && arr2 == null) {
      return true;
    }
    if (arr1.length != arr2.length) {
      return false;
    }
    for (int i = 0; i < arr1.length; i++) {
      if (arr1[i] != arr2[i]) {
        return false;
      }
    }
    return true;
  }
  //打印数组
  public static void printArray(int[] arr) {
    if (arr == null) {
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
      int[] arr1 = generateRandomArray(maxSize, maxValue);
      int[] arr2 = copyArray(arr1);
      selectionSort(arr1);
      comparator(arr2);
      if (!isEqual(arr1, arr2)) {// 相同返回1，不相同返回0
        printArray(arr1);
        printArray(arr2);
        break;
      }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    int[] arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    selectionSort(arr);
    printArray(arr);
  }
}

由于只有核心部分代码不一样，所以只放核心部分代码

2）冒泡排序

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    for (int e = arr.length - 1; e > 0; e--) {// 0~e
      for (int i = 0; i < e; i++) {
        if (arr[i] > arr[i + 1]) {
          swap(arr, i, i + 1);
        }
      }
    }
  }

3）插入排序

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {// 0~0位置上有序
      return;
    }
    // 1~i位置上有序
    for (int i = 1; i < arr.length; i++) {
      for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
        swap(arr, j, j + 1);
      }
    }
  }

认识随机函数

Math.random()：[0,1)范围上所有的小数等概率返回一个（前闭后开）
Math.random()*N：[0,N)
(int)(Math.random()*N)：[0,N-1]
[0,N]：(int)(N+1)* ((maxValue+1)*Math.random());
[-?,+?]：(int)((maxValue+1)* Math.random())-(int)(maxValue*(maxValue+1) *Math.random());

认识二分法

在一个有序数组中：1）找某个数是否存在；2）找>=某个数最左侧的位置；3）找<=某个数最右侧的位置

1）找某个数是否存在

package com.harrison.one;
import java.util.Arrays;
//在一个有序数组中，找某个数是否存在
public class Class04_BSExist {
  // 二分法核心代码
  public static boolean exist(int[] sortedArr, int num) {
    if (sortedArr == null || sortedArr.length == 0) {
      return false;
    }
    int L = 0;
    int R = sortedArr.length - 1;
    int mid = 0;
    while (L < R) {
      mid = L + ((R - L) >> 1);
      if (num == sortedArr[mid]) {
        return true;
      } else if (num < sortedArr[mid]) {
        R = mid - 1;
      } else {
        L = mid + 1;
      }
    }
    return sortedArr[L] == num;
  }
  //另写的一个方法,不使用二分法
  public static boolean test(int[] sortedArr, int num) {
    for (int cur : sortedArr) {
      if (cur == num) {
        return true;
      }
    }
    return false;
  }
  // 产生随机数组，长度随机，且值也随机
  public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
  }
  public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 10;
    int maxValue = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
      int[] arr = generateRandomArray(maxSize, maxValue);
      Arrays.sort(arr);
      int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
      if (test(arr, value) != exist(arr, value)) {
        succeed = false;
        break;
      }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
  }
}

2）找>=某个数最左侧的位置

package com.harrison.one;
import java.util.Arrays;
//在一个有序数组中,找>=某个数最左侧的位置
public class Class05_BSNearLeft {
  // 在arr上，找>=value的最左位置
  public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1;// 记录最左的对号
    while (L <= R) {
      int mid = L + ((R - L) >> 1);
      if (value <= arr[mid]) {
        R = mid - 1;
        index = mid;
      } else {
        L = mid + 1;
      }
    }
    return index;
  }
  //另写的一个方法，不使用二分
  public static int test(int[] arr, int value) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] >= value) {
        return i;
      }
    }
    return -1;
  }
  // 产生随机数组，长度随机，且值也随机
  public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
  }
  // 打印数组
  public static void printArray(int[] arr) {
    if (arr == null) {
      return;
    }
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 10;
    int maxValue = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
      int[] arr = generateRandomArray(maxSize, maxValue);
      Arrays.sort(arr);
      int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
      if (test(arr, value) != nearestIndex(arr, value)) {
        printArray(arr);
        System.out.println(value);
        System.out.println(test(arr, value));
        System.out.println(nearestIndex(arr, value));
        succeed = false;
        break;
      }
    }
    System.out.println(succeed ? "Nice!" : "Fucking fucked!");
  }
}

3）找<=某个数最右侧的位置

// 在arr上，找<=value的最右位置
  public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1;// 记录最右的对号
    while (L <= R) {
      int mid = L + ((R - L) >> 1);
      if (value >= arr[mid]) {
        L = mid + 1;
        index = mid;
      } else {
        R = mid - 1;
      }
    }
    return index;
  }

补充

使用二分法时，mid=(L+R)/2，如果L和R数值很大很大时，mid会溢出，所以比较好的一种方式是写成：

mid=L+(R-L)/2 => mid=L+((R-L)>>1); >>：带符号右移1位；>>>：不带符号位右移（不管最高位是0还是1，都用0来补）。

另一个写成这样的原因就是位运算就是比除运算快！！！

4）局部最小值问题

题目：给定一个数组，无序，任意两个相邻的数都不相等，返回任意一个局部最小

分析：可以用二分法，不一定要有序才能二分！只要有二分的标准，在二分的过程中，有一种排他性的原则出现，就可以二分！！！

关键代码：mid>mid-1 => right=mid-1 mid>mid+1 => left=mid+1

public static int getLessIndex(int[] arr) {
    if(arr==null || arr.length==0) {
      return -1;//no exist
    }
    if(arr.length==1 || arr[0]<arr[1]) {
      return 0;
    }
    if(arr[arr.length-1]<arr[arr.length-2]) {
      return arr.length-1;
    }
    int left=1;
    int right=arr.length-2;
    int mid=0;
    while(left<right) {
      mid=(left+right)/2;
      if(mid>mid-1) {
        right=mid-1;
      }else if(mid>mid+1) {
        left=mid+1;
      }else {
        return mid;
      }
    }
    return left;
  }

认识异或运算

异或运算：相同为0，不同为1
同或运算：相同为1，不同为0

容易记混！更好的记忆方式：异或运算即无进位相加

异或运算的性质

0^N==N
N^N==0
异或运算满足交换律和结合律（即同样一批数异或的结果与顺序无关）

利用异或运算的性质进行骚操作

1）不用额外变量交换两个数

int a=甲 int b=乙
a=a^b
b=a^b
a=a^b

前提：a和b不能指向同一片内存，哪怕值相同也行，但是就是不能指向同一片内存

2）一个数组中有一种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这种数

3）怎么把一个整型的数，提取出最右侧的1来 => int Ans=N&((~N)+1)

4）一个数组中有两种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数

5）给出一个数，求该数二进制1的个数

public static int bit1Counts(int N) {
    int count=0;
    // N    00100110100
    // rightOne 00000000100
    // N    00100110000
    // rightOne 00000010000 
    while(N!=0) {
      int rightOne=N&((~N)+1);
      count++;
      N^=rightOne;
    }
    return count;
  }

代码：

package com.harrison.one;
//一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
public class Class07_EvenTimesOddTimes {
  //arr中，只有一种数，出现奇数次
  public static void printOddTimesNum1(int [] arr) {
    int eor=0;
    for(int i=0; i<arr.length; i++) {
      eor^=arr[i];
    }
    System.out.println(eor);
  }
  //arr中，有两种数，出现奇数次
  public static void printOddTimesNum2(int [] arr) {
    int eor=0;
    for(int i=0; i<arr.length; i++) {
      eor^=arr[i];
    }
    //eor==a^b
    //因为a和b不相等，所以eor!=0
    //eor必然在某个位置上有1
    //找eor最右侧的1
    int rightOne=eor&((~eor)+1);
    int onlyOne=0;//eor'
    for(int i=0; i<arr.length; i++) {
      //如果一个数 和 一个位置上有1的数 按位与 不等于0，说明这个数的这个位置上为1
      if((arr[i]&rightOne)!=0) {
        //eor'重新异或arr数组，但是只异或最右侧位置上为1的数
        onlyOne^=arr[i];
      }
    }
    System.out.println(onlyOne+" "+(eor^onlyOne));
  }
  //给出一个数，求该数二进制1的个数
  public static int bit1Counts(int N) {
    int count=0;
    // N    00100110100
    // rightOne 00000000100
    // N    00100110000
    // rightOne 00000010000 
    while(N!=0) {
      int rightOne=N&((~N)+1);
      count++;
      N^=rightOne;
    }
    return count;
  }
  public static void main(String[] args) {
    int a = 5;
    int b = 7;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    System.out.println(a);
    System.out.println(b);
    int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
    printOddTimesNum1(arr1);
    int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
    printOddTimesNum2(arr2);
  }
}

1.复杂度、对数器、二分法与异或运算

三大排序算法

1）选择排序

2）冒泡排序

3）插入排序

认识随机函数

认识二分法

1）找某个数是否存在

2）找>=某个数最左侧的位置

3）找<=某个数最右侧的位置

补充

4）局部最小值问题

认识异或运算

异或运算的性质

利用异或运算的性质进行骚操作

1）不用额外变量交换两个数

2）一个数组中有一种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这种数

3）怎么把一个整型的数，提取出最右侧的1来 => int Ans=N&((~N)+1)

4）一个数组中有两种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数

5）给出一个数，求该数二进制1的个数

热门文章

最新文章

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

1.复杂度、对数器、二分法与异或运算

三大排序算法

1）选择排序

2）冒泡排序

3）插入排序

认识随机函数

认识二分法

1）找某个数是否存在

2）找>=某个数最左侧的位置

3）找<=某个数最右侧的位置

补充

4）局部最小值问题

认识异或运算

异或运算的性质

利用异或运算的性质进行骚操作

1）不用额外变量交换两个数

2）一个数组中有一种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这种数

3）怎么把一个整型的数，提取出最右侧的1来 => int Ans=N&((~N)+1)

4）一个数组中有两种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数

5）给出一个数，求该数二进制1的个数

热门文章

最新文章

相关电子书

相关实验场景