数组

• 写一个算法，可以将一个二维数组顺时针旋转90度，说一下思路。

考察点：数组
参考回答：

public void
rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n/2; i++) {
            for (int j = i; j < n-1-i; j++)
{
                int temp = matrix[i][j];
                matrix[i][j] =
matrix[n-1-j][i];
                matrix[n-1-j][i] =
matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] =
matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
}

• 一个数组，除一个元素外其它都是两两相等，求那个元素?

考察点：数组
参考回答：

 public static int find1From2(int[] a){
        int len = a.length, res = 0;
        for(int i = 0; i < len; i++){
            res= res ^ a[i];
        }
        return res;
}

• 找出数组中和为S的一对组合，找出一组就行

考察点：数组
参考回答：

public int[]
twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map =
new HashMap<Integer, Integer>();
        int[] a = new int[2];
        map.put(nums[0], 0);
        for (int i = 1; i < nums.length;
i++) {
            if (map.containsKey(target - nums[i])) {
                a[0] = map.get(target -
nums[i]);
                a[1] = i;
                return a;
            } else {
                map.put(nums[i], i);
            }
        }
        return a;
}

• 求一个数组中连续子向量的最大和

考察点：数组
参考回答：

public int
maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        if (nums == null || nums.length == 0) {
            return sum;
        }
        for (int i = 0; i < nums.length;
i++) {
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
}

• 寻找一数组中前K个最大的数

考察点：数组
参考回答：

public int
findKthLargest(int[] nums, int k) {
    if (k < 1 || nums == null) {
        return
0;
    }
  
    return getKth(nums.length - k +1, nums, 0,
nums.length - 1);
}
  
public int
getKth(int k, int[] nums, int start, int end) {
  
    int pivot = nums[end];
  
    int left = start;
    int right = end;
  
    while (true) {
  
        while
(nums[left] < pivot && left < right) {
            left++;
        }
  
        while
(nums[right] >= pivot && right > left) {
            right--;
        }
  
        if
(left == right) {
            break;
        }
  
        swap(nums,
left, right);
    }
  
    swap(nums, left, end);
  
    if (k == left + 1) {
        return
pivot;
    } else if (k < left + 1) {
        return
getKth(k, nums, start, left - 1);
    } else {
        return
getKth(k, nums, left + 1, end);
    }
}
  
public void
swap(int[] nums, int n1, int n2) {
    int tmp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = tmp;
}