【Java】二分查找、冒泡排序、摩尔投票法（求多数元素）、调整数组奇数位于偶数前、判断连续奇数、找数组中两个元素和为另一个元素、寻找单身狗

Zzzzmo_

814人浏览 · 2025-08-26 16:47:53

Zzzzmo_ · 2025-08-26 16:47:53 发布

一、将数组当中的每个数据扩大2倍

创建临时数组

思路：写一个方法，创建一个临时数组，将传递过来的原数组中的每一个元素*2，然后赋值给临时数组

public class Test{
    public static int[] fun(int[] array){
        int[] ret = new int[array.lenght];
        for(int i = 0;i < array.lenght; i++){
            ret[i] = array[i]*2;
        }
        return ret;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        System.out.println(Arrays.toString(array));
        fun(array);
        System.out.println(Arrays.toString(array));
    }
}

在数组本身上扩大

public class Test{
    public static void fun(int[] array){
        for(int i = 0;i < array.lenght; i++){
            array[i] = array[i]*2;
        }
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        System.out.println(Arrays.toString(array));
        fun(array);
        System.out.println(Arrays.toString(array));
    }
}

二、数组转字符串

前面我们学习的用工具类 Arrays 的 toString 方法可直接将数组转换为字符串

也可以自己实现一个：

public class Test{
    public static String myToString(int[] array){
        String ret = "[";
        for(int i = 0;i < array.lenght; i++){
            ret += array[i];
            if(i != array.lenght-1){
                ret += ",";
            }
        }
        ret += "]";
        return ret;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        System.out.println(myToString(array));
        
    }
}

三、求数组中元素的平均值

给定一个整型数组，求平均值

public class Test{
    public static double fun(int[] array){
        int sum = 0;
        for(int x : array){
            sum += x;
        }
        return (double)sum / (double)array.lenght;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        double ret = fun(array);
        System.out.println(ret);
    }
}

四、查找数组中指定元素（顺序查找）

给定一个数组, 再给定一个元素, 找出该元素在数组中的位置

public class Test{
    public static int findNum(int[] array,int key){
        for(int i = 0;i < array.lenght; i++){
            if(array[i] == key){
                return i;
            }
        }
        return -1;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        int index = findNum(array,6);
        System.out.println(index);
    }
}

但是这样的查找效率低，因为它是一个个查找的，针对有序数组, 可以使用更高效的二分查找

查找数组中指定元素(二分查找)

必须是有序数组

啥叫有序数组?

有序分为 "升序" 和 "降序"

如 1 2 3 4 , 依次递增即为升序. 如 4 3 2 1 , 依次递减即为降序.

思路：先取中间位置的元素, 然后用待查找元素与数组中间元素进行比较

定义一个变量left表示数组第一个元素的下标，right表示数组最后一个元素，再定义一个变量mid，表示数组的中间元素。
如果要查找的元素与mid相等，则返回该数组元素的下标，如果要查找的元素小于mid，则只需要在 left ~ mid-1 的元素之间查找，再计算出这个区间的mid值，重复进行比较，找出等于mid的元素，返回其下标，如果大于mid，则只需要在 mid+1 ~ right 之间查找，和小于类似。

注意：可以从left查找到right，即 left <= right

public class Test{
    public static int binarySearch(int[] array,int key){
        int left = 0;
        int right = array.lenght-1;
        while(left <= right){
            int mid = (right + left) / 2;
            if(array[mid] == key){
                return mid;
            }else if(array[mid] > key){
                right = mid -1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        int index = binarySearch(array,6);
        System.out.println(index);
    }
}

如果数组是一个无序数组，那么一定要先排序再进行查找，使用 Arrays 类的 sort 方法进行排序（默认从小到大排序）：

public class Test{
    public static int binarySearch(int[] array,int key){
        int left = 0;
        int right = array.lenght-1;
        while(left <= right){
            int mid = (right + left) / 2;
            if(array[mid] == key){
                return mid;
            }else if(array[mid] > key){
                right = mid -1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,31,4,15};
        System.out.println("排序前的数组:" + Arrays.toString(array));
        
        Arrays.sort(array);

        System.out.println("排序后的数组:" + Arrays.toString(array));

        int index = binarySearch(array,15);
        System.out.println(index);
    }
}

除了自己实现一个二分查找，Array 中也有 binarySearch 方法可以直接求出数组中要找的元素的下标:

int[] array = {1,2,31,4,15};
System.out.println("排序前的数组:" + Arrays.toString(array));
        
Arrays.sort(array);

System.out.println("排序后的数组:" + Arrays.toString(array));

int index = Arrays.binarySearch(array,15);
System.out.println(index);

而Arrays类的binarySearch方法有许多的重载（toString、sort等都是）：

例如，binarySearch方法可以在指定位置查找：

int index3 = Arrays.binarySearch(array1,1,3,4);//在这个区间内查找：[1,3)
System.out.println(index3);//2

五、数组排序（冒泡排序）

给定一个数组, 让数组升序 (降序) 排序.

思路(假设排升序)：

1. 将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来后最大元素就在数组的末尾

2. 依次从上上述过程，直到数组中所有的元素都排列好

public class Test{
    public static void bubbleSort(int[] array){
        for(int i = 0;i < array.lenght-1; i++){
            boolean flag = false;//表示不需要进行交换，是升序排列
            for(int j = 0;j < array.lenght-1-i; j++){
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;//如果需要交换，即进入到循环内，就将flag改为true
                }
            }
        }
        if(flag == false){ //如果走到这里flag还是等于false，则说明原本就是一个升序序列，直接返回
            return;
        }
    }
    
    public static void main(String[] args){
        int[] array = {1,2,31,4,15};
        System.out.println("排序前的数组:" + Arrays.toString(array));
        
        bubbleSort(array);

        System.out.println("排序后的数组:" + Arrays.toString(array));
    }
}

六、数组拷贝

思路：写一个方法，创建一个新的数组，这个数组的长度和要拷贝的原数组的长度一样，将原数组中的元素拷贝到新的数组中

public class Test{
    public static void bubbleSort(int[] array){
        int[] copy = new int[array,lenght];
        for (int i = 0; i < array.length; i++) {
            copy[i] = array[i];
        }
        return copy;
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        int[] copy = copyArray(array);
        System.out.println(Arrays.toString(copy));
    }
}

使用 Arrays 的 copyOf 方法进行数组的拷贝--使用 copyOf 方法需要创建一个新数组，新数组的长度与要拷贝的数组一样：

int[] newCopy = Arrays.copyOf(array,array.lenght);
System.out.println(Arrays.toString(newArray));

利用copyOf方法的重载，还可以对数组进行扩容：

//进行扩容
int[] coPy = Arrays.copyOf(array,array.length*2);
System.out.println(Arrays.toString(coPy));

七、数组逆序

给定一个数组, 将里面的元素逆序排列.

思路：设定两个下标, 分别指向第一个元素和最后一个元素. 交换两个位置的元素，然后让前一个下标自增, 后一个下标自减, 循环继续即可。

public class Test{
    public static void reverse(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left < right){
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            left++;
            right--;
        }
    }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        System.out.print("逆序前的数组:");
        System.out.println(Arrays.toString(array));
        reverse(array);
        System.out.print("逆序后的数组:");
        System.out.println(Arrays.toString(array));
    }
}

八、调整数组顺序使得奇数位于偶数之前，调整之后，不关心大小顺序

思路：设定两个下标, 分别指向第一个元素left和最后一个元素right,如果left在走的过程中发现是奇数，则++，而right在走的过程中，发现是偶数，则++，如果都不是这些情况，就需要进行交换

public class Test{
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
    public static void fun(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left < right){
            while(left < right && array[left] % 2 != 0){
                left++;
                    
            }
            while(left < right && array[right] % 2 == 0){
                right--;
            }
            swap(array,left,right);
        }
    
    public static void main(String[] args){
        int[] array = {1,2,3,4,5,6};
        fun(array);
        System.out.println(Arrays.toString(array));
    }
}

九、给定一个整数数组nums和一个整数目标值target，找出该数组和为target的那两个整数，并返回它们的下标

假设每种输入只会对应一个答案，数组中同一个元素在答案中不会重复出现

思路：创建一个新的数组，将两个元素的下标存放在数组中，首先从数组的第一个元素开始，除了它之外的元素都和它一个个相加，如果遍历完，没有找到和为target的两个整数，则i++，j++，继续重复上面的操作。

public class Test{
    public static void fun1(int[] array,int target){
        int[] ret = new int[2];
        for(int i = 0;i < array.lenght; i++){
            for(int j = i+1;j < array.lenght; j++){
                if(array[i] + array[j] == target){
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
        return ret;
    }
    
    public static void main(String[] args){
        int[] array = {2,7,11,15};
        int[] ret = fun1(array,9);
        System.out.println(Arrays.toString(ret));
    }
}

十、寻找单身狗

给一个非空整数数组，除了某元素只出现一次之外，其余每个元素均出现两次，找出只出现一次的元素

思路:将数组的每一个元素都进行按位异或^（相同为0，相异为1，0^n=n n^n=0）

public class Test{
    public static int fun2(int[] array){
        int ret = 0;
        for (int i = 0; i < array.length; i++){
            ret ^= array[i];
        }
        return ret;
    }
    
    public static void main(String[] args){
        int[] array = {1,1,2,2,3};
        int ret = fun2(array);
        System.out.println(ret);
    }
}

十一、给定一个大小为n的数组，找到其中的多数元素，多数元素是指在数组中出现次数大于 n/2 的元素

摩尔投票法

基本思想：每次从序列里选择两个不同的数字删除掉（或称为“抵消”），最后剩下的一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

算法步骤：
1. 初始化一个候选元素candidate和计数器count。遍历数组，对于每个元素：
2. 如果count为0，则将当前元素设为候选元素candidate。
3. 如果当前元素等于candidate，则count加1；否则，count减1。
4. 遍历结束后，candidate就是可能的多数元素，直接返回candidate。

例如，数组 [3,2,3]：
第一步：i=0:count=0，candidate=3，count=1
第二步：i=1:当前元素2不等于3，count减1变为0
第三步：i=2:count=0，所以candidate更新为3，count=1
最后返回3。

另一个例子 [2,2,1,1,1,2,2]：

i=0: num=2 -> candidate=2, count=1
i=1: num=2 -> candidate=2, count=2
i=2: num=1 -> candidate=2, count=1
i=3: num=1 -> candidate=2, count=0 (因为1不等于2，所以减1，变成0)
i=4: 此时count=0，所以设置candidate=当前元素1，count=1
i=5: num=2 -> 当前元素2不等于candidate(1)，所以count减1，变成0
i=6: 此时count=0，所以设置candidate=当前元素2，count=1
最后返回candidate=2。

public class Test{
    public static int fun3(int[] array){
        int candidate = array[0];//设置候选元素candidate为数组的第一个元素，计数器 count 为1
        int count = 1;
        for(int i = 1;i < array.lenght; i++){ //从第二个元素开始遍历数组
            if(count == 0){  //如果count减为0，则将下一个元素设为新的candidate,并将count重置为1
                candidate = array[i];
                count = 1;
            }else if(candidate == array[i]){ //如果当前元素等于 candidate，则 count 加1
                count++;
            }else{    //否则，count 减1
                count--;
            }
            
        }
        return candidate;//遍历结束后 candidate 即为多数元素
    }
    
    public static void main(String[] args){ 
        int[] array = {2,2,1,1,1,2,2};
        int candidate = fun3(array);
        System.out.println(candidate);
    }
}

十二、给一个整数数组arr,判断数组中是否存在连续三个元素都是奇数的情况，如果存在，请返回true，否则返回false

思路：设置一个计数器count，如果是在遍历时，是奇数就置为1，偶数就置为0

例如：如果开始遍历时第一个元素是奇数，count=1，下一个也是奇数，count=2，再下一个如果是偶数，则count=0，再继续往下遍历，直到出现count=3，则说明有三个连续的奇数，如果count没有等于3，则说明没有。

public class Test{
    public static boolean fun4(int[] array){
        int count = 0;
        for (int i = 0; i < array.length; i++){
            if(array[i] % 2 != 0){
                count++;
                if(count == 3){
                    return true;
                }
            }else{
                count = 0;
            }
        }
        return false;
    }
    
    public static void main(String[] args){ 
        int[] array = {1,2,34,3,4,5,7,23,12};
        System.out.println(fun4(array));
    }
}