Как удалить массив с отрицательными числами

Question

Я пытался решить следующую проблему,

Дан массив целых чисел, каждый элемент появляется в три раза, за исключением для одного. Найдите этот единственный.

Когда вход все положительны, я не буду получать какие-либо ошибки, но когда вход содержит отрицательные числа, линия delete index; даст ошибку, кто-нибудь знает почему?

т.е.

A[] = {1,2,3,4,1,2,3,4,1,3,4} работает отлично, но A[] = {-2,-2,1,1,-3,1,-3,-3,-4,-2} не делает.

Код выглядит следующим образом,

#include <iostream> 
#include <map> 

class Solution { 
public: 
    int singleNumber(int A[], int n) { 
     // IMPORTANT: Please reset any member data you declared, as 
     // the same Solution instance will be reused for each test case. 

     int *index; 
     std::map<int, int> m; 

     index = new signed int[(n+1)/3]; 
     int flag = 0; 
     int result; 

     for(int i=0; i<n; i++) { 
      if(m.find(A[i]) == m.end()) { 
       m[A[i]] = 1; 
       index[flag] = A[i]; 
       flag++; 
      } else { 
       m[A[i]] = m[A[i]] + 1; 
      } 
     } 

     for(int i=0; i<(n+1)/3; i++) { 
      if(m[index[i]] != 3) { 
       result = index[i]; 
      } 
     } 

     delete index; 

     return result; 
    } 
}; 

int main() 
{ 
    Solution s; 

    int A[] = {1,2,3,4,1,2,3,4,1,3,4}; 
    int result = s.singleNumber(A, 11); 
    std::cout <<result; 

    return 0; 
} 

Answer 1

Первый массив содержит 11 элементов, что приводит к линии index = new signed int[(n+1)/3]; выделить массив (11 + 1)/3 = 4 элементов. Второй массив содержит 10 элементов, что заставляет эту строку выделять массив из (10 + 1)/3 = 3 элементов.

3 элемента недостаточно для записи уникальных значений в A (-4, -3, -2 и 1), поэтому вы переполняете массив.

Вы должны выделить не менее (n+2)/3 элементов. Было бы также разумно проверить значение flag, чтобы оно никогда не превышало границы массива. Это не будет, если входной массив подчиняется ограничению, что каждый элемент, кроме одного, появляется три раза (предполагается, что это означает, что он появится один или два раза, а не четыре или более), но можете ли вы полагаться на это ограничение, которому подчиняются?

Кроме того, петля for(int i=0; i<(n+2)/3; i++) недостаточна для повторения всех элементов, которые были добавлены на карту. Вы должны быть уверены, что выполняете итерацию всех членов m.

---

Кстати, singleNumber могут быть реализованы в гораздо более увлекательным способом без каких-либо динамических вызовов распределения или библиотеки:

int singleNumber(int A[], int n) { 
    int b = 0, c = 0; 
    while (n--) 
    { 
     b ^= A[n] & c; 
     c ^= A[n] & ~b; 
    } 
    return c; 
} 

Однако, это совсем не то, что ваш инструктор ожидает.