Перейти к содержанию
Вывести неповторяющиеся элементы массива
Просмотров 6.1к. Обновлено 15 октября 2021
В массиве найти элементы, которые в нем встречаются только один раз, и вывести их на экран. То есть найти и вывести уникальные элементы массива.
Будем брать очередной элемент массива и сравнивать его со всеми остальными элементами массива от начала до конца. Если при сравнении два элемента окажутся равны друг другу, и при этом элемент не сравнивается сам с собой, то значит этот «исследуемый» элемент не уникальный. Дальнейшее сравнение этого элемента не имеет смысла, и надо перейти к следующему. Если же ни одного совпадения не было найдено, значит элемент не повторяется в массиве, и его надо вывести на экран.
В программе можно использовать переменную-флаг. Перед началом проверки уникальности элемента присвоить ей, например, значение 1. Если совпадение будет найдено, то присвоить флагу 0. Если же после всех сравнений флаг остался равен 1, то значит элемент массива не повторяется в нем.
Pascal
уникальные элементы массива паскаль
const N = 20;
var
a: array[1..N] of word;
i,j: byte;
flag: boolean;
begin
randomize;
for i:=1 to N do begin
a[i] := random(15);
write(a[i],' ');
end;
writeln;
for i:=1 to N do begin
flag := True;
for j:=1 to N do
if (a[i] = a[j]) and (j <> i) then begin
flag := False;
break;
end;
if flag = True then
write(a[i],' ');
end;
writeln
end.
12 5 7 6 5 13 5 1 1 14 1 3 13 4 13 4 3 9 11 9
12 7 6 14 11
Язык Си
уникальные элементы массива c++
#include
#define N 20
main() {
unsigned short a[N], i, j, f;
srand(time(NULL));
for (i=0; i< N; i++) {
a[i] = rand() % 15;
printf("%d ", a[i]);
}
printf("n");
for (i=0; i< N; i++) {
f = 1;
for (j=0; j< N; j++)
if (a[i] == a[j] && i != j) {
f = 0;
break;
}
if (f == 1) printf("%d ", a[i]);
}
printf("n");
}
7 9 5 11 1 11 10 11 5 14 10 9 6 14 6 13 6 11 0 9
7 1 13 0
Python
уникальные элементы массива Python (питон)
from random import random
N = 20
a = [0] * N
for i in range(N):
a[i] = int(random()*15)
print(a[i],end=' ')
print()
for i in range(N):
f = True
for j in range(N):
if a[i] == a[j] and i != j:
f = False
break
if f == True:
print(a[i],end=' ')
print()
1 3 2 8 12 6 10 6 13 11 6 4 10 9 2 8 7 13 1 9
3 12 11 4 7
Basic-256
N = 20
dim a(N)
for i=0 to N-1
a[i] = int(rand * 15)
print a[i] + " ";
next i
for i=0 to N-1
f = 1
for j=0 to N-1
if a[i] = a[j] and i <> j then
f = 0
endif
next j
if f = 1 then print a[i] + " ";
next i
12 1 8 10 14 3 7 1 14 5 5 2 14 13 3 9 14 10 12 11
8 7 2 13 9 11
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given an array arr[] of size N and an integer T representing the count of threads, the task is to find all non-repeating array elements using multithreading.
Examples:
Input: arr[] = { 1, 0, 5, 5, 2}, T = 3
Output: 0 1 2
Explanation:
The frequency of 0 in the array arr[] is 1.
The frequency of 1 in the array arr[] is 1.
The frequency of 2 in the array arr[] is 1.
Therefore, the required output is 0 1 2Input: arr[] = { 1, 1, 5, 5, 2, 4 }, T = 3
Output: 2 4
Explanation:
The frequency of 2 in the array arr[] is 1.
The frequency of 4 in the array arr[] is 1.
Therefore, the required output is 2 4
Approach: The idea is to use the pthread library available in C++ to create multiple threads for concurrent process flow and perform multiple operations( pthread create, pthread join , lock, etc) in multithreaded program. Follow the steps below to solve the problem:
- Divide the array into T subarrays, such that each subarray of size N / T will be executed in a single thread.
- Initialize a Map, say mp, to store the frequencies of each array element.
- Create a pthread_mutex_lock, say lock1, to ensure that all threads do not trip over each other and corrupt the Map container.
- Define a function func() for executing the body of a thread. This function is often called the kernel of the thread and is provided during thread creation.
- Lock the current thread using pthread_mutex_lock() so that it does not overlap with other threads
- Traverse through the given range as an argument to the function func() in the array arr[] and increment the frequency of the array element which is encountered.
- Release the current thread using the function pthread_mutex_unlock().
- Initialize an array, say thread[], of type pthread_t for storing the threads.
- Iterate over the range [0, T] and create a thread by calling pthread_create() function and store it in the thread[i]
- While each thread performs their individual tasks, the main() function will need to wait till each of the threads finish their work.
- Use pthread_join() function for waiting till each thread finishes executing function func()
- Iterate over the range [0, T] and call pthread_create() function for each thread[i]
- Finally, traverse the map mp and print the element occurring only once.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <pthread.h>
using namespace std;
struct range_info {
int start;
int end;
int* a;
};
map<int, int> mp;
pthread_mutex_t lock1;
void* func(void* arg)
{
pthread_mutex_lock(&lock1);
struct range_info* rptr
= (struct range_info*)arg;
for (int i = rptr->start;
i <= rptr->end; i++) {
map<int, int>::iterator it;
it = mp.find(rptr->a[i]);
if (it == mp.end()) {
mp.insert({ rptr->a[i], 1 });
}
else {
it->second++;
}
}
pthread_mutex_unlock(&lock1);
return NULL;
}
void numbers_occuring_once(int arr[],
int N, int T)
{
pthread_t threads[T];
int spos = 0;
int epos = spos + (N / T) - 1;
for (int i = 0; i < T; i++) {
struct range_info* rptr
= (struct range_info*)malloc(
sizeof(struct range_info));
rptr->start = spos;
rptr->end = epos;
rptr->a = arr;
int a
= pthread_create(&threads[i], NULL,
func, (void*)(rptr));
spos = epos + 1;
epos = spos + (N / T) - 1;
if (i == T - 2) {
epos = N - 1;
}
}
for (int i = 0; i < T; i++) {
int rc
= pthread_join(threads[i], NULL);
}
for (auto it: mp) {
if (it.second == 1) {
cout << it.first << " ";
}
}
}
int main()
{
pthread_mutex_init(&lock1, NULL);
int T = 3;
int arr[] = { 1, 0, 5, 5, 2, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
numbers_occuring_once(arr, N, T);
}
Java
import java.util.HashMap;
import java.util.Map;
public class Main {
static class RangeInfo {
int start;
int end;
int[] a;
RangeInfo(int start, int end, int[] a)
{
this.start = start;
this.end = end;
this.a = a;
}
}
static Map<Integer, Integer> mp = new HashMap<>();
static void func(RangeInfo rptr)
{
for (int i = rptr.start; i <= rptr.end; i++) {
int curr = rptr.a[i];
synchronized (mp)
{
Integer freq = mp.get(curr);
if (freq == null) {
mp.put(curr, 1);
}
else {
mp.put(curr, freq + 1);
}
}
}
}
static void numbersOccurringOnce(int[] arr, int n,
int t)
{
Thread[] threads = new Thread[t];
final int spos = 0;
final int epos = spos + (n / t) - 1;
for (int i = 0; i < t; i++) {
final int start = spos + (n / t) * i;
final int end
= i == t - 1 ? n - 1
: spos + (n / t) * (i + 1) - 1;
RangeInfo rptr = new RangeInfo(start, end, arr);
threads[i] = new Thread(() -> func(rptr));
}
for (int i = 0; i < t; i++) {
threads[i].start();
}
for (int i = 0; i < t; i++) {
try {
threads[i].join();
}
catch (InterruptedException e) {
e.printStackTrace();
}
}
for (Map.Entry<Integer, Integer> it :
mp.entrySet()) {
if (it.getValue() == 1) {
System.out.print(it.getKey() + " ");
}
}
}
public static void main(String[] args)
throws InterruptedException
{
Object lock1 = new Object();
int T = 3;
int[] arr = { 1, 0, 5, 5, 2, 6 };
int N = arr.length;
numbersOccurringOnce(arr, N, T);
}
}
C#
using System;
using System.Collections.Generic;
using System.Threading;
class RangeInfo {
public int start;
public int end;
public int[] a;
public RangeInfo(int start, int end, int[] a)
{
this.start = start;
this.end = end;
this.a = a;
}
}
public class GFG {
static Dictionary<int, int> mp
= new Dictionary<int, int>();
static void func(RangeInfo rptr)
{
for (int i = rptr.start; i <= rptr.end; i++) {
int curr = rptr.a[i];
lock(mp)
{
int freq;
mp.TryGetValue(curr, out freq);
if (freq == 0) {
mp.Add(curr, 1);
}
else {
mp[curr] = freq + 1;
}
}
}
}
static void numbersOccurringOnce(int[] arr, int n,
int t)
{
Thread[] threads = new Thread[t];
int spos = 0;
int epos = spos + (n / t) - 1;
for (int i = 0; i < t; i++) {
int start = spos + (n / t) * i;
int end = i == t - 1
? n - 1
: spos + (n / t) * (i + 1) - 1;
RangeInfo rptr = new RangeInfo(start, end, arr);
threads[i] = new Thread(() => func(rptr));
}
for (int i = 0; i < t; i++) {
threads[i].Start();
}
for (int i = 0; i < t; i++) {
threads[i].Join();
}
foreach(KeyValuePair<int, int> entry in mp)
{
if (entry.Value == 1) {
Console.Write(entry.Key + " ");
}
}
}
public static void Main(string[] args)
{
int T = 3;
int[] arr = { 1, 0, 5, 5, 2, 6 };
int N = arr.Length;
numbersOccurringOnce(arr, N, T);
}
}
Python3
import threading
class RangeInfo:
def __init__(self, start, end, a):
self.start = start
self.end = end
self.a = a
mp = {}
def func(rptr):
for i in range(rptr.start, rptr.end + 1):
curr = rptr.a[i]
with threading.Lock():
freq = mp.get(curr, 0)
if freq == 0:
mp[curr] = 1
else:
mp[curr] = freq + 1
def numbersOccurringOnce(arr, n, t):
threads = []
spos = 0
epos = spos + (n // t) - 1
for i in range(t):
start = spos + (n // t) * i
end = n - 1 if i == t - 1 else spos + (n // t) * (i + 1) - 1
rptr = RangeInfo(start, end, arr)
threads.append(threading.Thread(target=func, args=(rptr,)))
for thread in threads:
thread.start()
for thread in threads:
thread.join()
for key, value in mp.items():
if value == 1:
print(key, end=" ")
if __name__ == "__main__":
T = 3
arr = [1, 0, 5, 5, 2, 6]
N = len(arr)
numbersOccurringOnce(arr, N, T)
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Note: It is recommended to execute the program in a Linux based system using the following command:
g++ -pthread program_name.cpp
Last Updated :
20 Apr, 2023
Like Article
Save Article
Создаем массив чисел от 1 до 75, с помощью рандома чисел от 1 до 75 начинаем поиск элемента в массиве. Совпал – удалили. Ищем дальше. Совпал – удалили. Не нашли элемент – ищем снова пока не найдем.
Вот что вышло:
int[]array;
int num = (int)(Math.random()*75+1);//имитируем выпадение числа от 1 до 75
public int[] initArray(){//создаем, инициализируем и заполняем массив цифрами от 1 до 75 включительно
this.array = new int[75];
for (int i = 0; i < array.length; i++){
array[i] = i+1;
}
return array;
}
public static int findNumberInMass(int[] array, int num) {
for (int i = 0; i < array.length; i++) {
if (num == array[i]) {
return i + 1;
}
}
return 0;//вот тут он должен не найти нужный элемент и перезапустить поиск
}
Прошу помощи, а то голова кипит.
Как сделать так, чтоб он находил элемент выпавший в рандоме, искал его в массиве и удалял?
И чтоб он искал совпадения, а если не нашел то перезапускал рандом?
vp_arth
27.1k2 золотых знака45 серебряных знаков76 бронзовых знаков
задан 8 фев 2017 в 18:09
9
Более простое решение, есть класс(барабан), в котором при создании появляется N шаров, из которого мы можем достать случайный шар из оставшихся, с помощью getNext.
import java.util.LinkedList;
public class Game
{
private LinkedList<Integer> drum;
public Game(int N) {
drum = new LinkedList<Integer>();
for (int i = 0; i < N; i++) {
drum.add(i+1);
}
}
public int getNext() {
if (drum.size() == 0) throw new java.lang.IndexOutOfBoundsException("No items more");
final int i = (int)Math.floor(Math.random()*(drum.size()-1));
return drum.remove(i);
}
}
public class HelloWorld
{
public static void main(String[] args)
{
System.out.println("6 of 36 game");
int N = 36;
Game game = new Game(N);
for (int i = 0; i < 6; i++) {
int selected = game.getNext();
System.out.println("Item "+selected+ " was selected!");
}
}
}
ответ дан 8 фев 2017 в 19:45
vp_arthvp_arth
27.1k2 золотых знака45 серебряных знаков76 бронзовых знаков
3
Если я правильно понял задачу, то приведённый ниже код иллюстрирует её решение.
class Main {
private final static int[] numbers = initArray();
// Заполнение массива numbers числами от 1 по 75.
private static int[] initArray() {
final int[] array = new int[75];
for (int i = 0; i < array.length; ++i)
array[i] = i + 1;
return array;
}
// Поиск позиции числа n в массиве numbers. Возвращает -1, если число не найдено.
private static int findNumber(final int n) {
for (int i = 0; i < numbers.length; ++i)
if (numbers[i] == n)
return i;
return -1;
}
// Получение следующего случайного числа.
private static int nextRandom() {
while (true) { // В бесконечном цикле...
final int n = (int)(Math.random()*75+1); // ... берём случайное число, ...
final int pos = findNumber(n); // ... и ищем его в массиве numbers.
if (pos >= 0) { // Если число найдено, ...
numbers[pos] = -1; // ... то "удаляем" его...
return n; // ... и завершаем цикл, ...
}
} // ... иначе возвращаемся к началу.
}
public static void main(final String[] args) {
for (int ignored : numbers)
System.out.println(nextRandom());
}
}
Здесь применена небольшая хитрость. Во-первых, если мы не нашли число в массиве, то возвращаем заведомо невалидный индекс (-1). А во-вторых, поскольку удаление элемента массива выполнить без создания нового массива невозможно, то во избежание этой “дорогостоящей” операции мы просто помещаем в массив на место этого числа опять-таки заведомо невалидное значение (-1).
ответ дан 8 фев 2017 в 19:00
5
Вариант решения с использованием ArrayList:
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(); // создание динамического массива
Random r = new Random();
for (int x = 0; x < 75; x++) {
list.add(r.nextInt(76)); // заполнение массива случайными цифрами до 75
}
System.out.println("Initial list = " + list); // вывод заполненного массива в консоль
while (list.size() > 0) { // выполняем цикл пока размер массива не уменьшиться до 0
for (int x = 0; x < list.size(); x++) {
int num = r.nextInt(76); // выбираем случайное число для поиска в массиве
if (list.get(x) == num) { // сопоставляем случайное число с элементами массива
list.remove(x); // удаляем элемент в случае совпадения
System.out.println(num + " was deleted");
System.out.println(list); // выводим оставшийся массив
}
}
}
System.out.println("Array is empty"); // по исчерпанию элементов массива
}
ответ дан 11 фев 2017 в 23:05
SergeySergey
1165 бронзовых знаков
Просто и без лишних заморочек:
public static void main(String[] args) {
//Исходное значение макс. числа
int length = 75;
//Булевый массив, где помечается, какое из чисел использовалось.
//По-умолчанию каждый элемент инициализируется как false
boolean[] arr = new boolean[length];
//Просто для наглядности общего кол-ва попыток найти число.
int totalIterations = 0;
//Всего должно будет вывестись 75 чисел,
//поэтому ставим данное условие в цикле, но итерацией будем заниматься внутри
for (int i = 0;i<length;){
//Получаем рандомное значение
final int n = (int)(Math.random()*length+1);
//Если элемент с этим значением не был использован
if (!arr[n-1]){
//Выводим его в консоль
System.out.println(n);
//Помечаем как использованный
arr[n-1] = true;
//Производим итерацию
i++;
}
//Дополнительно считаем общее кол-во итераций
totalIterations++;
}
//Уведомляем об окончании
System.out.println("Done! Total iterations: "+totalIterations);
}
Вариант с альтернативным подходом:
public static void main(String[] args) {
//Исходное значение макс. числа
int length = 75;
//Кол-во перемешиваний
int mixes = 1000;
//Выводим итоговый результат
for (int i: initArr(length,mixes)){
System.out.println(i);
}
}
static int[] initArr(int length, int mixes) {
//Инициализируем массив
int[] result = new int[length];
//Заполняем значениями
for (int i = 0; i < length; i++)
result[i] = i+1;
//Проходим по циклу заданное кол-во перемешиваний
for (int i = 0; i < mixes; i++) {
//Получаем рандомное первое значение
final int first = (int)(Math.random()*length);
//Получаем рандомное второе значение
final int second = (int)(Math.random()*length);
//Меняем местами значение по полученным выше индексам
final int temp = result[first];
result[first] = result[second];
result[second] = temp;
}
return result;
}
ответ дан 9 фев 2017 в 13:22
I. PerevozI. Perevoz
9034 серебряных знака20 бронзовых знаков
3
Сегодня разберем одно из заданий, часто ставящее в тупик еще на этапе условия. Разберем как вывести неповторяющиеся элементы массива и напишем программу на языке C++.
Если описать задание немного более простым языком, то нам всего лишь нужно найти и вывести элементы массива, значения которых встречаются один раз. Проще говоря — уникальные значения элементов массива.
Имея массив [1, 3, 5, 8, 3, 8], мы должны вывести 1, 5. Почему? Потому что 3 и 8 встречаются в массиве больше одного раза.
Решений может быть несколько, давайте разберем самое простое. Мы будем брать каждый элемент массива и сравнивать его со всеми остальными, если совпадений не найдется, то мы просто его выводим и идем дальше.
Звучит довольно просто, но на деле нам понадобится цикл в цикле. Первым циклом будем проходить по всем элементам массива, а второй нужен будет для поиска совпадений.
Давайте реализуем алгоритм для вывода неповторяющихся элементов массива на C++
#include
using namespace std;
int main()
{
/* Заполним массив значениями */
int n = 6;
int mass[n] = {1, 3, 5, 8, 3, 8};
/* Проходим по всем элементам массива */
for (int i = 0; i < n; ++i) {
// Вынесем текущий элемент в переменную
int currentElementValue = mass[i];
// Имеет ли текущий элемент значение, встречающееся в массиве
// по умолчанию нет
bool hasEquals = false;
/* Берем элемент и ищем по массиву такое же значение */
for (int r = 0; r < n; ++r) {
// С самим с собой не сравниваем, пропускаем итерацию
if (i == r) {
continue;
}
// Если текущий элемент равен другому элементу
if (currentElementValue == mass[r] && i != r) {
// То устанавливаем флаг, что такое значение встречалось
hasEquals = true;
}
}
// Если у этого элемента нет встречающихся значений, то выводим
if (!hasEquals) {
cout << currentElementValue << " ";
}
}
return 0;
}
В программе я использовал такой же массив, котрый описал в условии. Компилируем, запускаем и видим вывод
1 5
То есть то, что необходимо.
|
DarkBatterfly |
|
|
1 |
|
Вывести на экран неповторяющиеся элементы массива09.02.2010, 14:35. Показов 6828. Ответов 6
Всем здрасте. Есть просьба подскажите пожалуйста ссылочку или книгу где нормально описаны массивы а то не могу разобраться в них. Ну и перейдём к к главному вопросу) Люди тут такое дело задали “Вывести на экран не повторяющиеся элементы массива” а не могу сделать. Может ктот подсказать что и как? За ранее премного благодарен. |
|
Day 1177 / 987 / 83 Регистрация: 29.10.2009 Сообщений: 1,385 |
||||
|
09.02.2010, 15:05 |
2 |
|||
0 |
|
5827 / 3478 / 358 Регистрация: 08.02.2010 Сообщений: 7,448 |
|
|
09.02.2010, 15:25 |
3 |
|
Есть просьба подскажите пожалуйста ссылочку или книгу где нормально описаны массивы а то не могу разобраться в них. Философия C++. Введение в стандартный C++ (Брюс Эккель) – неплохая книжка, там все подробно расписано, в том числе и массивы
0 |
|
Grayswandir 10 / 10 / 1 Регистрация: 05.02.2010 Сообщений: 12 |
||||
|
09.02.2010, 18:03 |
4 |
|||
0 |
|
shelest3 7 / 7 / 3 Регистрация: 08.02.2010 Сообщений: 8 |
||||
|
10.02.2010, 00:29 |
5 |
|||
|
Где-то так…
0 |
|
easybudda Модератор
11755 / 7256 / 1719 Регистрация: 25.07.2009 Сообщений: 13,264 |
||||
|
10.02.2010, 01:43 |
6 |
|||
Не, это не то немного!
0 |
|
DarkBatterfly |
|
|
12.02.2010, 12:21 |
7 |
|
спс всем за помощь) |
