想要面试过的去，必须每日一刷题！
关于Android面试这里我就不多讲了,直接上题。
面试题：
1.寻找数组中第二小的元素
- 直接排序（冒泡n^2、快排nlgn）根据索引找到对应值
- 遍历一次，定义两个变量：一个变量用来存储数组的最大数，初始值为数组首元素，另一个变量用来存储第二大的数。
编码：
1. public static void findSecond(int a[]){
2. if(a.length<3){
3. System.out.println("数组太小");
4. }
5. int max=0,min=0;
6. for (int i=1;i<a.length;i++){
7. if(a[i]>=a[i-1]&&i<2){//确定两个最大初始值
8. max=a[i];
9. min=a[i-1];
10. continue;
11. }
12. if(a[i]>max&&i>1){//大于最大值
13. min=max;
14. max=a[i];
15. }
16. if(a[i]<max&&a[i]>min&&i>1){//介于两者之间
17. min=a[i];
18. }
19. }
20. System.out.println("max:"+max);
21. System.out.println("min:"+min);
22. }
2.找到数组中第一个不重复出现的整数
- 用数组存储每个数字出现的次数，但题目只需要找到第一个不重复出现的数，故浪费空间，O（N^2）
- 双循环，找到第一个不重复，即返回，O(N^2)
编码1：
1. /**
2. 找出数组中第一个不重复的数字,如果没有就返回null
3. */
4. public class FirstDupNum {
5. @Test
6. public void start() {
7. int [] arr ={1,2,3,9,7,66,5,5,4,66,3,7,2,9,0,0,1,4};
8. System.out.println(handler(arr));
9. }
10. public Integer handler(int [] arr){
11. Integer position=null;
12. for (int i = 0; i < arr.length; i++) {
13. for (int j =0; j <arr.length ; j++) {
14. if(i!=j&&arr[i]==arr[j]){
15. position=j;
16. break;
17. }
18. if(j==arr.length-1){
19. position=arr.length;
20. }
21. }
22. if(position==arr.length){
23. return arr[i];
24. }
25. }
26. return null;
27. }
28. }
29. 编码2：
30. /**
31. 找出数组中第一个不重复的数字
32. */
33. #define Length(arr) (sizeof(arr)/sizeof(int))
34. void main() {
35. int arr[18] ={1,2,3,9,7,66,5,5,4,8,3,7,2,9,0,0,1,4};
36. handler(&arr,Length(arr));
37. }
38.
39. int handler(int *arr,int length){
for (int i = 0; i < length; i++) {
int count = 0;
for (int j = 0; j < length ; j++) {
if(i!=j&&arr[i]==arr[j]){
count++;
break;
}
}
if(count==0){
print("%d",arr[i]);
break;
}
}
return 0;
}
}
3.合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
示例:
- nums1 = [1,2,3,0,0,0], m = 3
- nums2 = [2,5,6], n = 3
- 输出: [1,2,2,3,5,6]
方法一:合并后,七大排序
这个方法有点生硬,我将nums2数组拷贝到nums1后面,然后得到一个无顺序的数组,这个时候我们学过的七大排序就派上用场了,这里我采用插入排序为例子：
1. class Solution {
2. public void merge(int[] nums1, int m, int[] nums2, int n) {
3. if (n == 0){
4. return;
5. }
6. for (int i = 0; i < nums2.length; i++) {
7. nums1[m + i] = nums2[i];
8. }
9. insertSort(nums1,m + n);
10. }
11. public void insertSort(int[] array,int length){
12. //这是插入排序
13. for (int bound = 1; bound < length; bound++) {
14. int tmp = array[bound];
15. int cur = bound - 1;
16. for(;cur >=0;cur--){
17. if (array[cur] > tmp){
18. array[cur + 1] = array[cur];
19. }else {
20. break;
21. }
22. }
23. array[cur + 1] = tmp;
24. }
25. }
26. }
时间复杂度:O(N^2)
空间复杂度:O(1)
方法二:合并后排序
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array.
意思是,将src数组拷贝到dest目标数组,从0(srcPos)开始拷贝,拷贝到目标数组从m(destPos)开始拷贝,拷n这么长
1. public void merge(int[] nums1, int m, int[] nums2, int n) {
2. System.arraycopy(nums2,0,nums1,m,n);
3. Arrays.sort(nums1);//排序
4. }
方法三:双指针法
这个方法有点类似合并两个有序链表
也是用两个指针,一个指向nums1(Copy),一个指向nums2,比较大小然后放入nums1中
具体实现代码如下:
1. public void merge(int[] nums1, int m, int[] nums2, int n) {
2. int[] nums1Copy = new int[m];
3. //将nums1新拷贝一份
4. System.arraycopy(nums1,0,nums1Copy,0,m);
//两个指针,一个指向nums1Copy,一个指向nums2
int p1 = 0;
int p2 = 0;
int p = 0;//指向nums1最终要输出的
while ((p1 < m) && (p2 < n)){
nums1[p++] = (nums1Copy[p1] < nums2[p2])? nums1Copy[p1++] : nums2[p2++];
}
if (p1 < m)
System.arraycopy(nums1Copy, p1, nums1, p, m - p1);
if (p2 < n)
System.arraycopy(nums2, p2, nums1, p ,n - p2);
}
4.重新排列数组中的正值和负值
给定一个包含正数和负数的整数数组，重新排列它，使得所有的负数排在前面，所有的正数排在后面。正数间和负数间的相对顺序保持不变。期望时间复杂度是O(n), 空间复杂度是O(1).
例如: 给定 [-1,2,-2,3,5,-4], 重新排列后变成 [-1,-2,-4,2,3,5]
分析：
- 最简单的算法是O(n^2), 遇到每个负数都把它移动到数组前面已经排列好的负数部分后面。
- O(n)的算法暂时没想出来，似乎比较难，下面给出一个O(nlogn)的算法。基本思想类似于Merge Sort. 空间复杂度由于用到递归，是O(logn). 不过可以很容易改写为bottom-up的迭代版本。
编码：
1.
void Main()
2. {
3. int[] nums = new int[] {-1, 2, -2, 3, 5, -4};
4.
5. Reorder(nums, 0, nums.Length-1);
6. }
7.
8. *// Define other methods and classes here*
9. public void Reorder(int[] nums, int start, int end)
10. {
11. if(start >= end) {
12. return;
13. }
14.
15. int middle = start + (end-start)/2;
16. Reorder(nums, start, middle);
17. Reorder(nums, middle+1, end);
18. Merge(nums, start, middle, end);
19. }
20.
21. private void Merge(int[] nums, int start, int end)
22. {
23. int i = start;
24. while(nums[i] < 0 && i <= end) i++;
25. int j = end;
26. while(nums[j] >= 0 && j >= start) j--;
27.
28. *// Shift the negative part to the front*
29. if(i < j) {
30. int k = j;
31. while(k>=i && nums[k]<0) k--;
32.
33. Reverse(nums, i, k);
34. Reverse(nums,k+1,j);
35. Reverse(nums,i,j);
36. }
37. }
38.
39. private void Swap(int[] nums, int i, int j)
40. {
41. int t = nums[i];
42. nums[i] = nums[j];
43. nums[j] = t;
44. }
45.
46. private void Reverse(int[] nums, int i, int j)
47. {
48. while(i < j) {
49. Swap(nums, i, j);
50. i++;
51. j--;
52. }
53. }
下面是自底向上的迭代版本。空间复杂度是O(1)。
1.
public void Reorder(int[] nums)
2. {
3. int n = nums.Length;
4.
5. for(int size = 1; size < n; size += size)
6. {
7. for(int low = 0; low < n-size; low+=size+size)
8. {
9. Merge(nums, low, Math.Min(low+size+size-1, n-1));
10. }
11. }
12. }
总结：
上面所述就是常常被问到的数据结构的数组面试题；后续还有算法、数据结构、Java面试、Android面试题。，我最近整理了许多，里面讲解的非常详细。领取《Android精选面经题纲》
https://docs.qq.com/doc/DUmVBQXNjdlBDTFNGAndroid精选面经题纲。
咱们下期见！
网友评论