急！急！急！面试时遇到几个算法题，求解

Question

第一：题时间复杂度我做的没有符合要求
第二题：疑问，1,9之间的差值大还是9,1之间的差值大？
第三题：是把所有的数都要输出吗？如果没有重复的，那又是按照什么样的排序规则，可以打乱原本的顺序吗？
第四题：你可以用冒泡,归并或者是快排public class QuictSortTest {
 public static void main(String...args){
  int[] arr=new int[]{23,4,5,6,23,45};
  quickSort(arr,0,arr.length-1);
  for(int i=0;i<arr.length;i++)
   System.out.print(arr[i]+"\t");
 }
 
 public static void quickSort(int[] a,int low,int high){
  if(low>=high)
   return;
  if(low<=high){
   int middle=partition(a,low,high);
   quickSort(a,low,middle-1);
   quickSort(a,middle+1,high);
  }
 } private static int partition(int[] a, int low, int high) {
  if(low>=high)
   return 0;
  int p=a[low];
  int i=low,j=high;
  while(i<j){
   while(i<=j&&i<a.length&&a[i]<=p){
    if(i<high)
     i++;
    else
     break;
   }
   while(i<=j&&a[j]>=p)
    j--;
   swap(a,i,j);
   if(i==j)
    break; //当情况是9,8,6,5这种的时候
  }
  swap(a,i,j);
  swap(a,low,j);
 
  return j;
 } 
 private static void swap(int[] a,int i, int j) {
  int tmp=a[i];
  a[i]=a[j];
  a[j]=tmp;
 }
 
}第五题：达不到要求
第六题：你可以考虑栈，以前写过一个迷宫就是使用栈的方法，如果是最短路径的话那么就需要深搜把所有的路径搜索出来，然后进行比较了。坐等高手

Answer 1

 第6题：采用堆栈的数据结构，使用宽度优先搜索算法，从起点开始，寻找出所有走一步所能到达的位置，记录这些位置，再从这些位置开始，寻找出所有
再走一步（即从起点走2步）所能到达的位置，不断继续，直到找到目标点止。然后从记录的这些位置中找出路径；
 具体的实现方法你可以看下这个网址：  http://blog.csdn.net/sunshinedabby/article/details/6284779

Answer 2

第二题：疑问，1,9之间的差值大还是9,1之间的差值大？一样大
第三题：是把所有的数都要输出吗？如果没有重复的，那又是按照什么样的排序规则，可以打乱原本的顺序吗？没有重复就都排个序就行啦
第四题：你可以用冒泡,归并或者是快排
我第四题什么算法都没用，就比较了一下，不知道对不对                        int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(arr[i] > max){
max = arr[i];
}
}
System.out.println(max);

Answer 3

请问LZ，第5题的a[i]数组，有什么其他限定条件吗？比方说a[i]中各个元素互不相同，或者a[i]为有序数列等等。

Answer 4

第5题,如果a的元素都>0的话,下面这段就可以了，如果有负数，就把所有元素都加同一个整数使得所有元素变正，不影响结果
int[] a = {2,3,4,5};
int s = 0;
int min = 0;
int max = 0;
for (int aa : a) {
if (max < aa)
max = aa;
}
int n[] = new int[max + a.length + 2];
for (int aa : a) {
n[aa] += 3;
}
for (int i = 0; i < n.length - 1; i++) {
n[i + 1] += n[i] / 2;
if ((n[i] = n[i] % 2) == 1)
s++;
}
System.out.println(s);

Answer 5

空间复杂度要求O(1)，你这个至少是O(n)了，而且万一有一个元素超大比如1000000000，难道你就创建一个这么大的int数组吗？
而且时间复杂度也有可能超过O(n)

Answer 6

使用a.length是为了防止极端情况,如果不考虑的话,用集合代替下到是可以少很多空间,不过极端情况就防不住了

Answer 7

关于synchronized的理解，希望高手给出答案

Answer 8

第五题可以不用算幂也不用求和。我们知道2的幂实际上就是1左移得到，比如pow(3)应该是1<<3的结果，换句话说就是第三位为1其余位为0即1000。
那么给定数组{2， 1， 3， 6}，求和后的结果应该是1001110（78），即第1， 2， 3， 6位为1，其余位为0。
再把sum*3转化为sum + sum + sum也就是{2， 1， 3， 6} + {2， 1， 3， 6} + {2， 1， 3， 6} = {2， 3， 1， 2， 3， 4， 6， 7}，合并一下相同的数得到结果{3， 1， 5， 6， 7} = 11101010 （234），合并规律为相同的数加1，{2， 2， 1} -〉 {3， 1}，只有1，3，5，6，7上为1其余地方为0，所以是5个1再来讨论负数的情况，pow(-1) = 1/2 = 0.5 二进制为0.1， 同样pow(-2) = 1/ 4 = 0.25 二进制为0.01，结论就是负多少就表示小数后面的第几位为1（仅2的幂是这样）。
那么数组{2, 1, 3, 6, -1, -3},求和后结果应该是1001110.101， sum * 3 =11100011.111，共8个1主要的问题是时间复杂度为n，空间复杂度为1

Answer 9

第一题：
就是时间复杂度达不到要求public class atest {
    public static void main(String[] args) {
        int[] a = { 2, 3, 1, 4 };
        int result = 0;
        for (int i = 0; i < a.length; i++) {
            result += findNumOfBigger(a, i);
        }
        System.out.println(result);
    }    public static int findNumOfBigger(int[] a, int index) {
        int count = 0;
        if (index >= a.length - 1 || index < 0)
            return 0;
        else {
            for (int i = index + 1; i < a.length; i++) {
                if (a[i] > a[index])
                    count++;
            }
            return count;
        }
    }
}