JavaSE——数组习题

​

文章目录

1. 二分查找
2. 两数之和
3. 只出现一次的数字
4. 多数元素
5. 存在连续三个奇数的数组
6. 奇数位于偶数之前
7. 求数组的平均值
8. 改变原有数组元素的值
9. 二分查找

 解题思路：

代码：

public class Test {

public static void main(String[] args) {
    int[] array = {1,2,3,4,5,6,7,8,9,10};
    int ret = binarySearch(array,9);
    System.out.println("找到了下标为："+ret);
}
public static int binarySearch(int[] array,int key){
    int right = array.length-1;
    int left = 0;

    while(left<=right){
        int mid = (left+right)/2;
        if(array[mid] == key){
            return mid;
        } else if (mid<key) {
            left = mid+1;
        }else {
            right = mid-1;
        }
    }
    return -1;
}

}

1. 两数之和

 解题思路：

public static void main(String[] args) {

    int[] array={1,3,6,7,9};
    int a = 8;
    sumnums(array,a);
    System.out.println(Arrays.toString(sumnums(array,a)));
}
public static int[] sumnums(int[] array,int target){
        int[] result = new int[2];
        for (int i=0;  i < array.length-1 ; i++) {
            for (int k = array.length-1; k>i; k--) {
                if((array[i]+array[k])==target){
                   result[0] = i;
                   result[1] = k;
                }
            }
        }
    return result;
}

}

1. 只出现一次的数字

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4
 解题思路：

异或的特点是：

1、n ^ n = 0；即两个相同的数字异或是0

2、0 ^ n = n；即0和任何数字进行异或，结果就是那个任何数字

用异或运算的性质可以巧妙的解决这个问题，因为数组中只有一个数字出现一次

其他出现两次的数字用异或运算后都是0，最终整个数组异或运算的结果即为所求

代码：

public class Test {

public static void main(String[] args) {

    int[] array = {2,2,1,1,3};
    int ret1 = onlynum(array);
    System.out.println(ret1);
}
public static int onlynum(int[] array){
    int ret=0;
    for (int i:array
         ) {
        ret^=i;
    }
    return ret;
}

}

1. 多数元素

示例 1：

输入：[3,2,3]
输出：3
示例 2：

输入：[2,2,1,1,1,2,2]
输出：2
解题思路：

给定的数组总是存在多数元素，意味着排好序之后，中间位置的数字一定是出现了大于 ⌊ n/2 ⌋ 的元素

import java.util.Arrays;

public class Test {

public static void main(String[] args) {
    int[] array = {1,1,1,1,2,3};
    int ret = majorityElement(array);
    System.out.println(ret);
}
public static int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

}

1. 存在连续三个奇数的数组

解题思路：

定义一个计数器，如果连续出现的次数超过3，则返回true ，注意这里count在遇见是偶数的情况时进行置零，不然判断的时整个数组有没有三个奇数

代码：

public class Test {

public static void main(String[] args) {
    int[] array = {1,2,3,5,7};
    boolean a = threenumisOdd(array);
    System.out.println(a);
}
public static boolean threenumisOdd(int[] array){
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        if(isOdd(array[i])) {
            count++;
            if (count == 3) {
                return true;
            }
        }
        else {
            count = 0;
        }
    }
    return false;
}
public static boolean isOdd(int num){
    return (num%2!=0);
}

}

1. 奇数位于偶数之前

解题思路：

使用2个下标，一个从0下标开始，一个从最后一个下标开始，左边下标寻找偶数，找到后右边下标寻找奇数，然后交换

为了防止出现全为奇数的情况，i>j越界，要注意循环条件加上i<j

 代码：

import java.util.Arrays;

public class Test {

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

}

1. 求数组的平均值

需要注意，平均值可能是小数

代码：

public class Test {

public static void main(String[] args) {
    int[] array = {1,2,3,4,5,6,7};
    System.out.println(avg(array));
}
public static double avg(int[] array){
    int sum=0;
    for (int i = 0; i < array.length; i++) {
        sum+=array[i];
    }
    return (sum*1.0/array.length);
}

}

1. 改变原有数组元素的值

两种方式，一种是在自己本身上进行扩大，一种是新的数组中扩大

import java.util.Arrays;

public class Test {

public static void main(String[] args) {
    int[] array = {1,2,3,4,5};
    func1(array);
    System.out.println(Arrays.toString(array));
}

//方式一：扩大的还是原来的数组，这样做的不好的地方是，改变了原来数组的值

public static void func1(int[] array) {

      for (int i = 0; i < array.length; i++) {

          array[i] = array[i]*2;

      }

  }

//方式二：扩大的新的数组，没有修改原来的值

public static int[] func2(int[] array) {

    int[] tmp = new int[array.length];//

    for (int i = 0; i < array.length; i++) {

        tmp[i] = array[i]*2;
 
    }
    return tmp;
}

}

​