T O P

[资源分享]     【Java数据结构与算法】简单排序、二分查找和异或运算

  • By - 楼主

  • 2021-07-21 00:00:10
  • 简单排序

    选择排序

    概念

    image
    首先,找到数组中最小的那个元素,其次,把它和数组的第一个元素交换位置(如果第一个元素就是最小的元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法叫做选择排序,因为它在不断地选择剩余元素中地最小者。

    代码实现

       public static void SelectionSort(int[] arr){
            if(arr==null||arr.length<2) return;     //去除多余情况
            int N = arr.length;
            for (int i = 0; i < N-1; i++) {
                int minIndex = i;
                for (int j = i+1; j < N; j++){
                    if(arr[j] < arr[minIndex]) minIndex = j;  //更新每一轮最小元素的下标
                }
                swap(arr,i,minIndex);
            }
        }
        public static void swap(int[] arr, int i, int j){     //交换元素
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    

    复杂度分析

    选择排序过程中,0~N-1 上任意位置i都要进行一次交换和N-1-i次比较。因此总共有N次交换和(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2次比较。
    也就是O(N^2)

    冒泡排序

    概念

    image
    从第一个元素开始遍历数组每两个元素一组比较,如果不满足从小到大的排序规则则进行交换,这样最后可以得到最大元素在数组最后的位置排好。如此往复,直到整个数组排好。

    代码实现

        public static void sort(int[] arr){
            if(arr==null||arr.length<2) return;      //去除多余情况
            for(int i = arr.length - 1; i >= 0;i--){ //外层反向遍历
                for(int j = 0;j < i; j++){
                    if(arr[j] > arr[j+1])
                        swap(arr,j,j+1);
                }
            }
        }
        public static void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    

    复杂度分析

    总的比较次数是(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2
    也就是O(N^2)

    插入排序

    概念

    image
    从左向右遍历,每次把遍历到的元素放到前面已经排好顺序的数组的合适位置。如此往复,直到整个数组排好。

    代码实现

        public static void sort(int[] arr){
            if(arr==null||arr.length<2) return;     //去除无效情况
            for(int i = 1; i < arr.length; i++){    //i从1开始,认为i为1时已经排好
                for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--)
                    swap(arr,j,j+1);
            }
        }
        public static void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    

    复杂度分析

    总的比较和交换次数都是(N-1)+(N-2)+……+1=N(N-1)/2~N^2/2
    也就是O(N^2)

    二分查找

    左侧边界二分查找

    在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 (arr[mid] >= value) {  //注意
                    index = mid;
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
            if(index == -1) return  -1;     //index可能为-1,防ArrayOutOfIndexException
            else if(arr[index] == value)
                return index;
            else return -1;
        }
    

    右侧边界二分查找

    在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 (arr[mid] <= value) {  //注意
                    index = mid;
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            if(index == -1) return  -1;     //index可能为-1,防止ArrayOutOfIndexException
            else if(arr[index] == value)
                return index;
            else return -1;
        }
    

    总结

    • 左侧边界二分查找
      先写if (arr[mid] >= value)
    • 右侧边界二分查找
      先写if (arr[mid] <= value)
    • 别忘了最后对index为-1做特殊处理,防止数组越界访问

    异或运算

    公式

    底层表现在二进制上,异或运算使得相同数字得0,不同数字得1
    1 ^ 1 = 0
    0 ^ 0 = 0
    1 ^ 0 = 1

    1 1 0 1 0 1 1 0
    ^ 0 1 0 0 1 1 0 0
    = 1 0 0 1 1 0 1 0

    0^N=N
    N^N=0
    满足交换律和结合律

    应用

    交换

    a=a^b
    b=a^b
    a=a^b
    实现了交换a,b的值
    注意:前提是a,b有不同的内存空间。如果a,b是数组下标,那么当a=b的时候不能使用该方法,因为a,b代表数组一块相同的空间。
    优点:位运算速度快,效率高

    常考面试题

    第一题

    在一组数中,只有一种数出现了奇数次,其他类型的数出现了偶数次,问这个出现奇数次的数是什么,时间复杂度小于O(N)

    解析:借助异或运算性质,N^N=0,只需要让所有数连续异或,最后的结果就是答案

        public static void printOddTimesNum1(int[] arr) {
    		int eO = 0;
    		for (int cur : arr) {
    			eO ^= cur;
    		}
    		System.out.println(eO);
    	}
    

    第二题

    在一组数中,有两种数出现了奇数次,其他类型的数出现了偶数次,问这两个出现奇数次的数是什么,时间复杂度小于O(N)

    解析:设这两个数是a和b,所以所有数字第一次连续异或可以得到a^b。下面我们只需要想办法搞出a或者b。
    举个例子,我们成功搞出a来,那么异或运算aba就可以得到b。注意到a和b前提是肯定不相同,那么在二进制的层面看这两个数字,它们肯定至少有一位数字是不一样的,一个是0,一个是1
    a:…………0001…………
    b:…………0000…………
    下面要做的就是把所有出现了两次的数字根据ab这一位不同的数字进行分组。
    这一位数字为0的数字为一组,这一位数字为1的数字为一组
    image
    让其中一组进行连续异或,比如这一位为1的这一组数字连续异或,出现偶数次的数字异或为0,最后只剩下a,我们就成功得到了a。
    最后进行a ^ b ^ a就可以得到b
    本题默认寻找a,b从右到左第一次出现的不同二进制位的位置,这也是本题的关键,等价于求ab异或后从右向左第一次出现1的位置。
    记住一个公式:原码和补码做与运算可以得到二进制数从右到左第一次出现1的位置为1,其他位置为0的数

    1010111100
    & 0101000100
    = 0000000100
        public static void printOddTimesNum2(int[] arr) {
    		int eO = 0, eOhasOne = 0;
    		for (int curNum : arr) {
    			eO ^= curNum;
    		}
    		int rightOne = eO & (~eO + 1);  原码和补码做与运算
    		for (int cur : arr) {
    			if ((cur & rightOne) == 1) { 该位是1的为一组
    				eOhasOne ^= cur;
    			}
    		}
    		System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
    	}
    

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册