java 数组的经典面试题_java数组的面试题

一、翻转数组

a.第一种方法:创建一个新数组接收
b.第二种方法:直接修改原数组;

public class TestArray {
	public static void main(String[] args) {
		
		int[] arr = new int[] {1,2,3,4,5};
		//定义一个新数组，把老数组中的元素反向添加到新数组中
		newArrReverse(arr);
  
		//在本数组上进行翻转
		ArrReverse(arr);
		
		
	}
	//定义一个新数组，把老数组中的元素反向添加到新数组中
	public static void  newArrReverse(int[] arr) {
		int[] brr = new int[arr.length];
		int length = arr.length - 1;  //定义一个从后向前的指针
		for (int i = 0; i < arr.length; i++) {
			brr[i] = arr[length];
			length --;
		}
		System.out.println(Arrays.toString(brr));
	}
	
	//在本数组上进行翻转
	public static void ArrReverse(int[] arr) {
		int temp = 0;
		int length = arr.length - 1;  //定义一个从后向前的指针
		for (int i = 0; i < arr.length; i++) {
			if (length == i) {
				break;
			}
			 temp = arr[i];
			 arr[i] = arr[length];
			 arr[length] = temp;
			 length --;
		}
		System.out.println(Arrays.toString(arr));
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

二、找数组当中重复的元素

第一种，两层for循环，指定一个循环一周 0(n^2)
类似于排序的思想（让下标i与它对应的数字相等）

思想：由于数组元素的范围是在0-n-1中，从头依次扫描数组中的每个数字，当扫描到下标为i的数字m时，
首先比较这个数字m与下标i是否相等，如果是则扫描下一个数字；
如果不是，则拿这个数字m和下标为m的数字进行比较。如果这个数字m和下标为m的数字相同，
就找到了第一个重复数字；如果不相同，则进行交换；直到下标i与对应的数字相等时，扫描下一个数字；
接下来重复这个比较；如下图所示：
1
2
3
4
5

public class TestArray {
	public static void main(String[] args) {
		
		int[] arr = new int[] {1, 2, 5, 5, 6, 6, 7, 2, 9, 2};
		
		findDupicateInArray(arr);
		
	}
	
	//第一种，两层for循环，指定一个循环一周   0(n^2)
	public static void  findDupicateInArray(int[] arr) {
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i+1; j < arr.length; j++) {
				if (arr[i] == arr [j]) {
					System.out.println("arr["+j+"]="+ arr[i] + "和" + "arr["+i+"]="+arr[i]+"冲突" + ", ");
				}
			}
			
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二种：数组排序完成后只要再扫描一次数组就可以确认有没有重复数字存在，也可以把所有重复数字找出。排序最快的时间复杂度是O(NlogN)。

第三种:另一种方式是在扫描的时候用哈希表来存储数组的每一个元素，当碰到数组元素与哈希表中一致时，可以确认数字重复。这样的方法时间复杂度是O(N)，但是需要临时空间O(N)。

//第三种：数组排序 完成后只要再扫描一次数组就可以确认有没有重复数字存在，也可以把所有重复数字找出。排序最快的时间复杂度是O(NlogN)。
	public static boolean duplicate(int numbers[],int length,int [] duplication) {
        Map<Integer,Integer> map=new HashMap<>();
        if(length==0) return false;
        for(int i:numbers){
            if(map.containsKey(i)){
               System.out.println("产生冲突的就是"+i);
            } 
            else map.put(i,0);
        }
        duplication[0]=-1;
        return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、调整数组顺序使奇数位于偶数前面

题目1：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有的数字往前面挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字，因此总的时间复杂度是O(n2）。但是，这种方法是不能让面试官满意的。不过如果我们在听到题目之后马上能够说出这个解法，面试官至少会觉得我们的思维非常灵敏。

这个题目要求把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面，也就是说我们在扫描这个数组的时候，如果发现有偶数在奇数的前面，我们可以交换他们的数序，交换之后就符合要求了。
因此我们可以维护两个指针，第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化时指向数组的最后一个数字，它指向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换两个数字。

基于这个分析，我们可以写出如下代码：

public class OddBeforeEven {
	public int[] recorderOddEven(int[] data, int length){
		if(data == null && length <= 0){
			return null;
		}
		
		int begin = 0;
		int end = length - 1;
		
		// begin指针要位于end指针前面
		while(begin < end){
			// 向后移动begin指针，直到它指向奇数
//			if(begin < end && (data[begin] & 0x1) != 0){
//				System.out.println(data[begin] + "****");
//				begin++;
//			}
			// 向后移动begin指针，直到它指向奇数
			if(begin < end && data[begin] %2 == 1) {
				System.out.println(data[begin] + "****");
				begin++;
			}
			// 向前移动end指针，直到它指向偶数
			if(begin < end && data[end] %2 == 0) {
				System.out.println(data[end] + "**//**");
				end--;
			}
			
//			// 向前移动end指针，直到它指向偶数
//			if(begin < end && (data[end] & 0x1) == 0){
//				System.out.println(data[end] + "**//**");
//				end--;
//			}

			// 交换奇数和偶数的位置
			if(begin < end){
				int temp = data[end];
				data[end] = data[begin];
				data[begin] = temp;
			}
		}
		return data;
	}
	
	// 测试
	public static void main(String[] args) {
		OddBeforeEven obe = new OddBeforeEven();
		int[] arr= {2,3,1,9,2,5,3};
		int[] data = obe.recorderOddEven(arr, arr.length);
		System.out.println(Arrays.toString(data));
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52