双指针以及数组移动和找出数组中只出现一次的数字

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 前言
• 一、双指针对数组中元素进行平方后再排序
• 二、利用“翻转”对数组进行向右移动n个位置
• 三、利用异或运算找出数组中只存在一次的数字

下面两个例子算法比较新颖，第一个例子为经典双指针

package double_point;

import java.util.Arrays;


public class TestOne {
    public int[] sortedSquares(int[] nums) {
        //利用sort排序
//        for(int i = 0;i=0){//当遍历指针还大于0的时候就继续循环
            nums1[i--] = nums[begin]*nums[begin]>nums[end]*nums[end]?nums[begin]*nums[begin++]:nums[end]*nums[end--];
        }//查看是在队尾的指针所指向的数字平方较大还是队首所指向的指针数字平方较大，大者则排入队列，并且大者所对应的指针也相应移动
        return nums1;
    }

    public static void main(String[] args) {
        int[] nums = {-4, -1, 0, 3, 10};
        TestOne testOne = new TestOne();
        int[] result = testOne.sortedSquares(nums);
        for(int v:result){
            System.out.print(v+",");
        }
    }
}

package double_point;

import com.sun.jdi.PathSearchingVirtualMachine;

import java.util.Arrays;


public class TestTwo {
    public void rotate(int[] nums, int k) {
        //利用java中自带的分离数组的方法
//        int len = nums.length;
//        k %= len;
//        System.out.println(k);
//        int[] tmp = Arrays.copyOfRange(nums,len-k-1,len-1);
//        for (int i = len - k - 1; i >= 0; i--) {
//            nums[i + k] = nums[i];
//        }
//        for (int i = 0; i < k; i++) {
//            nums[i] = tmp[i];
//        }
        int end = nums.length-1;
        reverse(nums,0,end);//将全部数字翻转
        reverse(nums,0,k-1);//将前k个元素进行翻转
        reverse(nums,k,end);//将后end-k个元素进行翻转
    }
    private void reverse(int[] nums,int begin,int end){//给定数组将其中所有的数字翻转
        while(end-begin>=1){
            nums[end] = nums[begin]+nums[end];
            nums[begin] = nums[end]-nums[begin];
            nums[end] = nums[end]-nums[begin];
            end--;
            begin++;
        }
    }

    public static void main(String[] args) {
        int[] nums = {-1,2,4,5,6};
        int k = 2;
        TestTwo testTwo = new TestTwo();
        testTwo.rotate(nums,k);
        for(int v:nums){
            System.out.print(v);
        }
    }
}

package double_point;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


public class TestThree {
    public int[] singleNumber(int[] nums) {
        int a = 0;
        for(int v:nums){//将所有的元素都异或起来，这样就是没有重复元素的两个元素的异或的结果
            a ^= v;
        }
        int i = 0;
        for(;i<31;i++){
            if((a>>i & 1)==1){//这两个数的异或结果进行二进制位移，当恰好为1的时候得出位移的次数i
                break;
            }
        }
        int[] result = new int[2];
        for(int v:nums){
            if((v>>i&1)==1){    //再次遍历整个数组，并且当元素位移i
                result[0] ^= v; //举个例子0110 ^ 1110 = 1000;当某一位相等的时候结果为0，不相等为1，当用1000>>3的时候为1，用0110>>3=0,11100>>3=1
            }else{              //其他相等的数字不用管，不相等的两个数字，去分别异或result[0]和result[1],所得的结果即为所求
                result[1] ^= v;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 3, 2, 5};
        TestThree testThree = new TestThree();
        System.out.println(Arrays.toString(testThree.singleNumber(nums)));
    }
}