During the two courses at the university, I realized that I could not program a damn thing. Now I want to solve this problem. To begin with, I think I need to figure out what I need to repeat. Algorithmic thinking is lame and knowledge of the language is lame. Here I am posting the puzzle I was trying to solve. Find the number of different elements in the array. Problems solved not correctly, but so far I can not figure out how to solve. With this task, I want to identify my gaps and get recommendations on how to eliminate them. Thanks in advance.

#include <iostream> using namespace std; int main() { const int size = 10; int arr[size] = { 10, 1, 1, 3, 1, 3, 1, 8, 9, 2 }; int count = 0; for (int i = 0; i < size; ++i) { for (int j = size - 1; j > i; --j) { if (arr[i] != arr[j]) { count++; break; } else --j; } } cout << count << endl; return 0; }
  • five
    @ArniLand Pull up need acceptance of responses. And then 0% of the accepted ... - Nicolas Chabanovsky ♦


4 answers 4

Absolutely not indicative code, from which it is clear only that you should pull up precisely the logical side of your thinking.

Such tasks are solved in a large number of ways, for example, by sorting the elements, followed by running through the array and counting the number of times when a[i-1] != a[i] , or emulating the set implemented on the array (let а[] be , representing the set, run through the input array of numbers c[] and do a[c[i]]=true , then count how many elements in the array a[] are true), and then trees, etc.

PS The method with a lot has a memory deficit will be wasted, so this is not the best choice, for me the sorting is the most, and for sorting you can use QuickSort (for thinking training), although of course the choice of sorting depends on many indicators, including and laziness :)

PSS My perverted mind also suggests that the set can be implemented on a bitmap :) it will turn out very compact)

  • one
    A small offtopic, I remembered the problem: there is an array of integers at the input from 0..MAXINT of enormous size (such that even the whole memory does not fit, of course, if you try to load it) and in this array all numbers are even number of times, and some odd one, you need to go through this array to find this number. It was solved very elegantly: it was necessary to perform the xor of all elements of the input sequence, the result was a response. (everything was based on the fact that 5 xor 5 = 0, 5 xor 6 xor 5 = 6) - GLAGOLA
  • If you need to keep the original array intact, then the bit set is better in terms of saving memory. - avp

Dear @ArniLand !

Do not be offended, but I am afraid that the reasoning in the wonderful answer @GLAGOLA will not give you much in terms of solving the problem. Check out the primitive solution.

 #include <stdio.h> #include <stdlib.h> /* Подсчет количества разных. */ int ndiff (int *arr, int size) { if (size <= 0) return 0; int /* set - 'как бы множество' т.е. сюда поместим элемент arr[], если такого еще нет. В конце работы количество элементов set[] это решение задачи. */ *set = malloc(sizeof(int)*size), i, j, n; // Это сколько уже поместили в set[] set[0] = arr[0]; // Хотя бы один должен быть даже если все одинаковые n = 1; for (i = 1; i < size; i++) { // Для каждого элемента массива for (j = 0; j < n; j++) { // просматриваем уже накопленное 'множество' if (set[j] == arr[i]) // такой уже встречался ? break; } if (j == n) // такого arr[i] еще не было set[n++] = arr[i]; // добавим его в 'множество' } free(set); return n; } main () { static int arr[] = {10, 1, 1, 3, 1, 3, 1, 8, 9, 2 }; int size = sizeof(arr)/sizeof(int); printf ("ndiff = %d\n",ndiff(arr,size)); exit(0); }

This program is terribly inefficient in memory and execution time, but it is extremely simple.

    The same program @avp (copy + paste), but a bit shorter.

     #include <iostream> #include <set> using namespace std; main () { static int arr[] = {10, 1, 1, 3, 1, 3, 1, 8, 9, 2 }; int size = sizeof(arr)/sizeof(int); set<int> s (arr, arr+size); cout << "Количество различных элементов " << s.size() << endl; return 0; }
    • I missed it, but only such a wonderful example, demonstrating standard C ++ library solutions, is unlikely to help the programmer to learn how to program. - avp
    • I think the opposite. Providing a solution without going into the subtleties of implementation is much more useful. Well, implement the same binary trees (or whatever is in the set ) - then it will be easier to learn. And do not underestimate the factor of laboriousness - to write out of curiosity ten lines or one hundred - there is a difference. - alexlz

    Sorry for the offtopic. If you want to improve your knowledge of C ++. Scott Meyers books will help you + read Stroustrup