Circular sorting
Pre-requisite : elements of the array should be between 1 to length of the array
In Circular Sorting elements are placed at their natural indexs
Example:if the array is [5,4,2,1,3] => [1,2,3,4,5]
class Solution {
public List<Integer> findDuplicates(int[] nums){
int i =0,n = nums.length;
while(i<n){
int j = nums[i]-1;
if(nums[i]!=nums[j]){
swap(nums,i,j);
}
else i++;
}
}
public void swap(int[] nums,int i ,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Usage:
Its useful in identifying duplicates in the array
It can also be used to find missing elements in the array
Example : Finding missing element in the array of length n where the elements of the array are in the range 0<=element<=n
class Solution {
public int missingNumber(int[] nums) {
int i =0,n = nums.length;
// circular sorting
while(i<n){
int j = nums[i]-1;
if(j<0) {i++ ; continue;}
else if(nums[i]!=nums[j]) swap(nums,i,j);
else i++;
}
int missing = 0;
for(int k = 0;k<nums.length;k++){
if(k!=nums[k]-1){ missing = k+1; break;}
}
return missing;
}
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Top comments (0)