2015年11月5日星期四

Leetcode 268 Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solution 1: iterate the array, swap nums[i] to position i. Then iterate again, find the one which i!=nums[i], otherwise it is n.
 public class Solution {  
   public int missingNumber(int[] nums) {  
     int n=nums.length;  
     for (int i=0; i<n; i++) {  
       while (nums[i]!=i && nums[i]<n) swap(nums,i,nums[i]);  
     }  
     for (int i=0; i<n; i++) {  
       if (i!=nums[i]) return i;  
     }  
     return n;  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

没有评论:

发表评论