轩辕互动面试1题

下午去轩辕互动面试了，可是第一轮就被刷了。没办法，没有那本事。
面试时问的是上一次做的一个题目：查找一个排好序的数组中绝对值不相同的数的个数。
我以前做的一个算法的复杂度为nlog(n), 晚上回来好好想了想，终于想出了一个O(n)的算法

public class DistinctCount{
	public static int distinctCount(int[] data){
		int start = 0;
		int end = data.length - 1;
		int count = 0;
		
		while(start <= end){
			while((start < (data.length - 1)) && (data[start] == data[start + 1]) && (start <= end)){
				start++;
				count++;
			}
			
			
			while((end > 0) && (data[end] == data[end - 1]) && (start <= end)){
				end--;
				count++;
			}
			
			if(start > end)
				break;
				
			if((data[start] == data[end]) || (data[start] + data[end] == 0)){
				start++;
				end--;
				count++;
			}else if(data[start] >= 0 || data[end] <= 0){
				start++;
			}else{
				if(data[start] + data[end] < 0)
					start++;
				else
					end--;
			}
		}
		
		return data.length - count + 1;
	}
	
	public static void main(String[] args){
		//int data[] = {-10, -10, -9, -9, -8, -7, -5, -3, 0, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 7, 7};
		int data[] = {1, 1, 1, 1, 1};
		System.out.println(DistinctCount.distinctCount(data));
	}
}

评论

2 楼 dodo452 2010-05-30  

其实很简单，红色字体为核心代码，本算法复杂度为O(n)
package dodo;

public class TestQuery {
    
   public static int statistic(int[] arr)
    {
    int count = 1;
int prior = Math.abs(arr[0]);
for(int i=1;i<arr.length;i++)
{
if(prior != Math.abs(arr[i]))
{
count++;
prior = Math.abs(arr[i]);
}
}

return count;

    }
   
   public static int[] sort(int [] arr)
   {
   for(int i =0;i<arr.length;i++)
   {
   for(int j=i+1;j<arr.length;j++)
   {
   if(arr[i]>arr[j])
   {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
   }
   }
   }
   return arr;
   }
  
   public static void show(int[] arr)
   {
  for(int i =0;i<arr.length;i++)
  {
  System.out.print(arr[i]+"\t");
  }
  System.out.println();
   }
    public static void main(String[] args) {
     int[] arr = new int[]{2,3,4,3,1,3,2,-1,-3,0};
     arr = sort(arr);
     show(arr);
     System.out.println(statistic(arr));
    }
}

1 楼 ryan.liu 2010-04-21  

public static int distinctCount(int[] data){
    int i = 0;
    int j = data.length-1;
    int last = -1;
    int count = 1;
    int p, q;
    //i向后移动，j向前移动
    while (i<j) { //没有相遇
        p = Math.abs(data[i]);
        q = Math.abs(data[j]);
        if (p>=q) { //向前移动
            i++;
            if (p!=last) { count++; }
            last = p;
        }
        else{ //向后移动
            j--;
            if (q!=last) { count++; }
            last = q;
        }
    }
    return count;
}