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]
import java.util.*; public class Main { public static void main(String[] args) { int arr[] = {5,4,2,1,3}; findDuplicates(arr); for(int i =0;i<arr.length;i++){ System.out.println(arr[i]); } } public static void 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 static 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)