Distintos elementos adyacentes en una array

Dada una array, encuentre si es posible obtener una array que tenga elementos vecinos distintos intercambiando dos elementos de array vecinos.

Ejemplos: 

Input : 1 1 2
Output : YES
swap 1 (second last element) and 2 (last element), 
to obtain 1 2 1, which has distinct neighbouring 
elements .

Input : 7 7 7 7
Output : NO
We can't swap to obtain distinct elements in 
neighbor .

Obtener una array que tenga distintos elementos vecinos solo es posible cuando la frecuencia de la mayoría de los elementos es menor o igual a la mitad del tamaño de la array, es decir ( <= (n+1)/2 ). Para hacerlo más claro considere diferentes ejemplos 

1st Example : 
    a[] = {1, 1, 2, 3, 1} 
    We can obtain array {1, 2, 1, 3, 1} by 
    swapping (2nd and 3rd) element from array a. 
    Here 1 occurs most and its frequency is 
    3 . So that 3 <= ((5+1)/2) .
    Hence, it is possible. 

A continuación se muestra la implementación de este enfoque. 

// C++ program to check if we can make
// neighbors distinct.
#include <bits/stdc++.h>
using namespace std;
 
void distinctAdjacentElement(int a[], int n)
{
    // map used to count the frequency
    // of each element occurring in the
    // array
    map<int, int> m;
 
    // In this loop we count the frequency
    // of element through map m .
    for (int i = 0; i < n; ++i)
        m[a[i]]++;
 
    // mx store the frequency of element which
    // occurs most in array .
    int mx = 0;
 
    // In this loop we calculate the maximum
    // frequency and store it in variable mx.
    for (int i = 0; i < n; ++i)
        if (mx < m[a[i]])
            mx = m[a[i]];
 
    // By swapping we can adjust array only
    // when the frequency of the element
    // which occurs most is less than or
    // equal to (n + 1)/2 .
    if (mx > (n + 1) / 2)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}
 
// Driver program to test the above function
int main()
{
    int a[] = { 7, 7, 7, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    distinctAdjacentElement(a, n);
    return 0;
}

# Python program to check if we can make
# neighbors distinct.
def distantAdjacentElement(a, n):
 
    # dict used to count the frequency
    # of each element occurring in the
    # array
    m = dict()
 
    # In this loop we count the frequency
    # of element through map m
    for i in range(n):
        if a[i] in m:
            m[a[i]] += 1
        else:
            m[a[i]] = 1
 
    # mx store the frequency of element which
    # occurs most in array .
    mx = 0
 
    # In this loop we calculate the maximum
    # frequency and store it in variable mx.
    for i in range(n):
        if mx < m[a[i]]:
            mx = m[a[i]]
 
    # By swapping we can adjust array only
    # when the frequency of the element
    # which occurs most is less than or
    # equal to (n + 1)/2 .
    if mx > (n+1) // 2:
        print("NO")
    else:
        print("YES")
 
 
# Driver Code
if __name__ == "__main__":
    a = [7, 7, 7, 7]
    n = len(a)
    distantAdjacentElement(a, n)
 
# This code is contributed by
# sanjeev2552

// C# program to check if we can make
// neighbors distinct.
using System;
using System.Collections.Generic;
 
class GFG {
 
public static void distinctAdjacentElement(int[] a, int n)
{
    // map used to count the frequency
    // of each element occurring in the
    // array
    Dictionary<int, int> m = new Dictionary<int, int>();
 
    // In this loop we count the frequency
    // of element through map m .
    for (int i = 0; i < n; ++i)
    {
 
        // checks if map already
        // contains a[i] then
        // update the previous
        // value by incrementing
        // by 1
        if (m.ContainsKey(a[i]))
        {
            int x = m[a[i]] + 1;
            m[a[i]] = x;
        }
        else
        {
            m[a[i]] = 1;
        }
 
    }
 
    // mx store the frequency
    // of element which
    // occurs most in array .
    int mx = 0;
 
    // In this loop we calculate
    // the maximum frequency and
    // store it in variable mx.
    for (int i = 0; i < n; ++i)
    {
        if (mx < m[a[i]])
        {
            mx = m[a[i]];
        }
    }
 
    // By swapping we can adjust array only
    // when the frequency of the element
    // which occurs most is less than or
    // equal to (n + 1)/2 .
    if (mx > (n + 1) / 2)
    {
        Console.WriteLine("NO");
    }
    else
    {
        Console.WriteLine("YES");
    }
}
 
    // Main Method
    public static void Main(string[] args)
    {
        int[] a = new int[] {7, 7, 7, 7};
        int n = 4;
        distinctAdjacentElement(a, n);
    }
}
 
// This code is contributed
// by Shrikant13

// Java program to check if we can make
// neighbors distinct.
import java.io.*;
import java.util.HashMap;
import java.util.Map;
class GFG {
 
static void distinctAdjacentElement(int a[], int n)
{
// map used to count the frequency
// of each element occurring in the
// array
HashMap<Integer,Integer> m = new HashMap<Integer,
Integer>();
 
// In this loop we count the frequency
// of element through map m .
for (int i = 0; i < n; ++i){
 
// checks if map already contains a[i] then
// update the previous value by incrementing
// by 1
if(m.containsKey(a[i])){
int x = m.get(a[i]) + 1;
m.put(a[i],x);
}
else{
m.put(a[i],1);
}
 
}
 
// mx store the frequency of element which
// occurs most in array .
int mx = 0;
 
// In this loop we calculate the maximum
// frequency and store it in variable mx.
for (int i = 0; i < n; ++i)
if (mx < m.get(a[i]))
mx = m.get(a[i]);
 
// By swapping we can adjust array only
// when the frequency of the element
// which occurs most is less than or
// equal to (n + 1)/2 .
if (mx > (n + 1) / 2)
System.out.println("NO");
else
System.out.println("YES");
}
 
// Driver program to test the above function
public static void main (String[] args) {
int a[] = { 7, 7, 7, 7 };
int n = 4;
distinctAdjacentElement(a, n);
}
}
// This code is contributed by Amit Kumar

<script>
 
// JavaScript program to check if we can make
// neighbors distinct.
 
 
function distinctAdjacentElement(a, n) {
    // map used to count the frequency
    // of each element occurring in the
    // array
    let m = new Map();
 
    // In this loop we count the frequency
    // of element through map m .
    for (let i = 0; i < n; ++i) {
        m[a[i]]++;
        if (m.has(a[i])) {
            m.set(a[i], m.get(a[i]) + 1)
        } else {
            m.set(a[i], 1)
        }
    }
    // mx store the frequency of element which
    // occurs most in array .
    let mx = 0;
 
    // In this loop we calculate the maximum
    // frequency and store it in variable mx.
    for (let i = 0; i < n; ++i)
        if (mx < m.get(a[i]))
            mx = m.get(a[i]);
 
    // By swapping we can adjust array only
    // when the frequency of the element
    // which occurs most is less than or
    // equal to (n + 1)/2 .
    if (mx > Math.floor((n + 1) / 2))
        document.write("NO" + "<br>");
    else
        document.write("YES<br>");
}
 
// Driver program to test the above function
 
let a = [7, 7, 7, 7];
let n = a.length;
distinctAdjacentElement(a, n);
 
</script>

NO

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Este artículo es una contribución de Surya Priy . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.