Program to remove duplicates numbers entirely from the sorted array in python

Question

Suppose we have a sorted list A. We have to return the length of the array after removing all duplicate entries. We have to perform this in O(1) extra space. So we have to do the operation in-place.

Nội dung chính Show

Example (Python)
How do I remove duplicates from a sorted array in Python?
How do you sort and remove duplicates in array?
How do you remove duplicate numbers in an array?
Does Python sorted remove duplicates?

For an example, suppose A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6] Then the output will be 6, as there are six distinct elements.

To solve this, follow these steps −

If the list is empty, return 0
otherwise, initially take prev = first element of A. And define length = 0
for i := 1 to n-1, do
- if A[i] is not the same as prev, then
  - length := length + 1
  - prev := A[i]
return length

Let us see the implementation to get a better understanding

Example (Python)

Live Demo

class Solution(object):
   def removeDuplicates(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      if len(nums) == 0:
         return 0
      length = 1
      previous = nums[0]
      index = 1
      for i in range(1,len(nums)):
         if nums[i] != previous:
            length += 1
            previous = nums[i]
            nums[index] = nums[i]
            index+=1
      return length
input_list = [1,1,2,2,2,3,3,3,3,4,5,5,5,6]
ob1 = Solution()
print(ob1.removeDuplicates(input_list))

Input

[1,1,2,2,2,3,3,3,3,4,5,5,5,6]

Output

Updated on 28-Apr-2020 15:59:22

Related Questions & Answers
Remove Duplicates from Sorted Array II in C++
Remove Duplicates from Sorted List in C++
Remove Duplicates from Sorted List II in C++
How to remove duplicates from a sorted linked list in android?
How to remove duplicates from the sorted array and return the length using C#?
How to remove duplicates from the sorted array and return the non-duplicated array using C#?
Removing duplicates from a sorted array of literals in JavaScript
Python - Ways to remove duplicates from list
Remove duplicates from a array of objects JavaScript
Remove duplicates from array with URL values in JavaScript
Java Program to Remove Duplicates from an Array List
Remove Consecutive Duplicates in Python
Remove all duplicates from a given string in Python
Remove array duplicates by property - JavaScript
Python program to remove Duplicates elements from a List?

View Discussion

Improve Article

Save Article

Read

Discuss

View Discussion

Improve Article

Save Article

Given a sorted array, the task is to remove the duplicate elements from the array.

Examples:

Input  : arr[] = {2, 2, 2, 2, 2}
Output : arr[] = {2}
         new size = 1

Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output : arr[] = {1, 2, 3, 4, 5}
         new size = 5

Method 1: (Using extra space)

Create an auxiliary array temp[] to store unique elements.
Traverse input array and one by one copy unique elements of arr[] to temp[]. Also keep track of count of unique elements. Let this count be j.
Copy j elements from temp[] to arr[] and return j

Implementation:

C++

#include <iostream>

using namespace std;

int removeDuplicates(int arr[], int n)

{

if (n == 0 || n == 1)

return n;

int temp[n];

int j = 0;

for (int i = 0; i < n - 1; i++)

if (arr[i] != arr[i + 1])

temp[j++] = arr[i];

temp[j++] = arr[n - 1];

for (int i = 0; i < j; i++)

arr[i] = temp[i];

return j;

}

int main()

{

int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

n = removeDuplicates(arr, n);

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

}

C

#include <stdio.h>

int removeDuplicates(int arr[], int n)

{

if (n == 0 || n == 1)

return n;

int temp[n];

int j = 0;

for (int i = 0; i < n - 1; i++)

if (arr[i] != arr[i + 1])

temp[j++] = arr[i];

temp[j++] = arr[n - 1];

for (int i = 0; i < j; i++)

arr[i] = temp[i];

return j;

}

int main()

{

int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };

int n = sizeof(arr) / sizeof(arr[0]);

n = removeDuplicates(arr, n);

for (int i = 0; i < n; i++)

printf("%d ", arr[i]);

return 0;

}

Java

class Main {

static int removeDuplicates(int arr[], int n)

{

if (n == 0 || n == 1)

return n;

int[] temp = new int[n];

int j = 0;

for (int i = 0; i < n - 1; i++)

if (arr[i] != arr[i + 1])

temp[j++] = arr[i];

temp[j++] = arr[n - 1];

for (int i = 0; i < j; i++)

arr[i] = temp[i];

return j;

}

public static void main(String[] args)

{

int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 };

int n = arr.length;

n = removeDuplicates(arr, n);

for (int i = 0; i < n; i++)

System.out.print(arr[i] + " ");

}

Python3

def removeDuplicates(arr, n):

if n == 0 or n == 1:

return n

temp = list(range(n))

j = 0;

for i in range(0, n-1):

if arr[i] != arr[i+1]:

temp[j] = arr[i]

j += 1

temp[j] = arr[n-1]

j += 1

for i in range(0, j):

arr[i] = temp[i]

return j

arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]

n = len(arr)

n = removeDuplicates(arr, n)

for i in range(n):

print ("%d"%(arr[i]), end = " ")

C#

using System;

class GFG {

static int removeDuplicates(int []arr, int n)

{

if (n == 0 || n == 1)

return n;

int []temp = new int[n];

int j = 0;

for (int i = 0; i < n - 1; i++)

if (arr[i] != arr[i+1])

temp[j++] = arr[i];

temp[j++] = arr[n-1];

for (int i = 0; i < j; i++)

arr[i] = temp[i];

return j;

}

public static void Main ()

{

int []arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};

int n = arr.Length;

n = removeDuplicates(arr, n);

for (int i = 0; i < n; i++)

Console.Write(arr[i] + " ");

}

Javascript

<script>

function removeDuplicates(arr, n)

{

if (n==0 || n==1)

return n;

var temp = new Array(n);

var j = 0;

for (var i=0; i<n-1; i++)

if (arr[i] != arr[i+1])

temp[j++] = arr[i];

temp[j++] = arr[n-1];

for (var i=0; i<j; i++)

arr[i] = temp[i];

return j;

}

var arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];

var n = arr.length;

n = removeDuplicates(arr, n);

for (var i=0; i<n; i++)

document.write( arr[i]+" ");

</script>

Time Complexity : O(n)
Auxiliary Space : O(n)

Method 2: (Constant extra space)

Just maintain a separate index for same array as maintained for different array in Method 1.

Implementation:

C++

#include<iostream>

using namespace std;

int removeDuplicates(int arr[], int n)

{

if (n==0 || n==1)

return n;

int j = 0;

for (int i=0; i < n-1; i++)

if (arr[i] != arr[i+1])

arr[j++] = arr[i];

arr[j++] = arr[n-1];

return j;

}

int main()

{

int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};

int n = sizeof(arr) / sizeof(arr[0]);

n = removeDuplicates(arr, n);

for (int i=0; i<n; i++)

cout << arr[i] << " ";

return 0;

}

Java

class Main

{

static int removeDuplicates(int arr[], int n)

{

if (n == 0 || n == 1)

return n;

int j = 0;

for (int i = 0; i < n-1; i++)

if (arr[i] != arr[i+1])

arr[j++] = arr[i];

arr[j++] = arr[n-1];

return j;

}

public static void main (String[] args)

{

int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};

int n = arr.length;

n = removeDuplicates(arr, n);

for (int i=0; i<n; i++)

System.out.print(arr[i]+" ");

}

Python3


# Python3 program to remove
# duplicate elements

# This function returns new 
# size of modified array
def removeDuplicates(arr, n):
    if n == 0 or n == 1:
        return n

    # To store index of next
    # unique element
    j = 0

    # Doing same as done
    # in Method 1 Just
    # maintaining another 
    # updated index i.e. j
    for i in range(0, n-1):
        if arr[i] != arr[i+1]:
            arr[j] = arr[i]
            j += 1

    arr[j] = arr[n-1]
    j += 1
    return j

# Driver code
arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
n = len(arr)

# removeDuplicates() returns
# new size of array.
n = removeDuplicates(arr, n)

# Print updated array
for i in range(0, n):
    print (" %d "%(arr[i]), end = " ")

C#

using System;

class GfG {

static int removeDuplicates(int []arr, int n)

{

if (n == 0 || n == 1)

return n;

int j = 0;

for (int i = 0; i < n - 1; i++)

if (arr[i] != arr[i + 1])

arr[j++] = arr[i];

arr[j++] = arr[n - 1];

return j;

}

public static void Main ()

{

int []arr = {1, 2, 2, 3, 4, 4,

4, 5, 5};

int n = arr.Length;

n = removeDuplicates(arr, n);

for (int i = 0; i < n; i++)

Console.Write(arr[i] + " ");

}

Javascript

<script>

function removeDuplicates(arr , n) {

if (n == 0 || n == 1)

return n;

var j = 0;

for (i = 0; i < n - 1; i++)

if (arr[i] != arr[i + 1])

arr[j++] = arr[i];

arr[j++] = arr[n - 1];

return j;

}

var arr = [ 1, 2, 2, 3, 4, 4, 4, 5, 5 ];

var n = arr.length;

n = removeDuplicates(arr, n);

for (i = 0; i < n; i++)

document.write(arr[i] + " ");

</script>

Time Complexity : O(n)
Auxiliary Space : O(1)

This article is contributed by Sahil Chhabra. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.

How do I remove duplicates from a sorted array in Python?

Practical Data Science using Python.

If the list is empty, return 0..

otherwise, initially take prev = first element of A. And define length = 0..

for i := 1 to n-1, do. if A[i] is not the same as prev, then. length := length + 1. prev := A[i].

return length..

How do you sort and remove duplicates in array?

We can remove duplicate element in an array by 2 ways: using temporary array or using separate index. To remove the duplicate element from array, the array must be in sorted order. If array is not sorted, you can sort it by calling Arrays. sort(arr) method.

How do you remove duplicate numbers in an array?

Following is the algorithm to delete the duplicate array's elements from the sorted array in the C programming language..

if (arr[i] != arr [i + 1].

temp [j++] = arr[i].

temp [j++] = arr[n- 1].

Repeat from i = 1 to j..

arr[i] = temp[i].

arr [i] = temp [i].

Return j..

Does Python sorted remove duplicates?

5. Using sort() We can use the sort() method to sort the set that we obtained in approach 2. This will also remove any duplicates, while preserving the order, but is slower than the dict.

programming python