银川商城网站开发设计,网站推广服务网站连锁,网站 目标,经典网站建设方案异或运算及异或运算实现的swap方法
^(异或): ^运算是计算机中的位运算#xff0c;运算规则为相同为0#xff0c;不同为1#xff08;也被称为无进位相加#xff09;。位运算处理效率比常规运算符效率更高。 异或运算遵循的法则#xff1a; 0^N N N^N 0 异或运算…异或运算及异或运算实现的swap方法
^(异或): ^运算是计算机中的位运算运算规则为相同为0不同为1也被称为无进位相加。位运算处理效率比常规运算符效率更高。 异或运算遵循的法则 0^N N N^N 0 异或运算遵循 结合律与交换律 也就是说a^a^bb swap方法的两种实现
常规交换推荐
public void swap(int[] arr,int i,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;
}
^交换(前提要求是arr[i]与arr[j]内存地址不同)
public void swap(int[] arr,int i,int j){arr[i] arr[i] ^ arr[j];arr[j] arr[i] ^ arr[j];arr[i] arr[i] ^ arr[j];
}
异或常见题 1.在一个数组中有一种数是奇数次其他数都是偶数次如何找出奇数次这种数[1,2,2,1,1,1,3,3,3]奇数次数为3 思路1.因为异或操作满足交换律所以数组可以写为 [1,1,1,1,2,2,3,3,3] 2.异或的特性 1^1 0 ;1^01 所以偶数项就消掉了只剩下一个奇数项了 public void problem1(int[] arr){int eor 0; // 0^i i;for(int i:arr){eor ^ i;}System.out.println(奇数项的数为eor);
} 2.在一个数组中有两种数是奇数次其他数都是偶数次如何找出奇数次这种[1,2,2,1,4,4,1,4,1,3,3,3] 奇数次数为34 思路1.数组所有数异或出来的结果肯定是 a^b 其中 a b必定是奇数项 2.因为a与b又不相等所以a^b的结果在2进制上某一位也比不相等(值称为rightOnerightOne 二进制表达为 0000 0100这种有规律的结构) 3.将数组划分为两个空间^rightOne的值被分为a所在区间或者b所在区间(根据结果等于1或者0判断)但是在这个区间里面只有a或者b 不存在ab同时存在的情况。 4.找到a 又知道a^b 所以 a^a^b b a、b两个结果都被求解出来了 public void problem2(int[] arr){int eor 0;for(int i:arr){eor ^i;}int rightOne eor (~eor 1);//a^b 源码与补码进行 操作 结果为 最右边二进制不相等的位次 int resultA 0;for(int i:arr){if(i^rightOne 1){//区间划分resultA ^i; }}int resultB eor^resultA;System.out.println({resultA ,resultB }); }
选择排序 public int[] selectSort(int[] arr){for(int i 0;i arr.length-1;i){ //该for循环保证在第i个位置上是[i,N]位置上的最小数int minIndex i;for(int j i1;j arr.length-1;j){//保证当前位置为整个数组最小值minIndex arr[i] arr[j] ? j : minIndex;}swap(arr,i,minIndex);}
}
//交换方法
public void swap(int[] arr,int i,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;
}
冒泡排序 public int[] bubbleSort(int[] arr){for(int i arr.length-1;i 0;i){//确定数组最右边的元素最大for(int j 0;j i;j){//对比数组中所有元素一步步的将最大的元素移植最右边if(arr[j] arr[j1]){//对比相邻数的大小进行交换swap(arr,j,j1);}}}return arr;
}
插入排序 public int[] insertSort(int[] arr){for(int i 1;i arr.length;i){//0-i位置上有序//向左判断数组大小如果当前位置小于前一个位置进行交换for((int j i-1;j 0 arr[j] arr[j1];j--){swap(arr,j,j1);}}}
对数器 什么是对数器对数器指的是在没有OJ平台在线程序测评系统时自测的一种方式。实现原理就是生成随机数据。例如数组长度随机数据随机的数组。将两套算法结果进行对比如果全部相同说明算法正确。其中一种算法是否正确未知另一种算法为暴力解法这种容易想并且不会错的座位对比项
package com.example.math;import java.util.Arrays;/*** author geekYang* version 1.0* since 1.0*/
public class 对数器 {public static void main(String[] args) {int maxSize 100;int maxValue 100;int testTotal 50000;//测试次数boolean succed true;for (int i 0; i testTotal; i) {int[] arr1 generateRandomArr(maxSize, maxValue);int[] arr2 Arrays.copyOf(arr1, arr1.length);comparator(arr1);insertSort(arr2);if (!Arrays.equals(arr1, arr2)) {succed false;break;}}System.out.println(succed ? Nice : Fucking fucked!);}//生成随机数组方法public static int[] generateRandomArr(int maxSize, int maxValue) {//(int) ((maxSize 1) * Math.random()) 生成随机[0,maxSize]范围的数int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i : arr) {arr[i] (int) ((maxSize 1) * Math.random()) - (int) ((maxSize 1) * Math.random());}return arr;}//对比方法public static int[] comparator(int[] arr) {for (int i 0; i arr.length - 1; i) {int minIndex i;for (int j i 1; j arr.length - 1; j) {minIndex arr[i] arr[j] ? j : minIndex;swap(arr, j, minIndex);}}return arr;}//测试方法public static int[] insertSort(int[] arr) {for (int i 1; i arr.length - 1; i) {for (int j i - 1; j 0 arr[j] arr[j 1]; j--) {swap(arr, j, j 1);}}return arr;}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}
}本文章根据左程云老师课程进行总结反思
